java - 来自 leetcode 的 Java 中的两个和

Question

我正在研究 leetcode 问题。我刚刚解决了以下问题:

给定一个整数数组，找到两个数字，使它们加起来等于特定的目标数字。

函数twoSum应该返回两个数字的索引，使它们相加达到目标，其中index1必须小于index2。请注意，您返回的答案(索引 1 和索引 2)不是从零开始的。

您可以假设每个输入都有一个解决方案。

输入:数字={2, 7, 11, 15}，目标=9输出:index1=1，index2=2

我的代码在这里:

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        
            int len = numbers.length;

        int[] result = new int[2] ;
        int number1 = 0;
        int sum = 0;

        for (int i = 0; i < len; i++) {
            number1 = numbers[i];

            for(int j = i+1; j < len; j++)
            {

                sum = number1+numbers[j];       
                if(sum == target)
                {
                    result[0]=i;
                    result[1]=j;
                }
            }
        
        }
        return result;
    }
}

它给了我一个超出的时间限制；但是，我认为这个解决方案可能有效。谁能告诉我这个解决方案是否足够好？

Answer 1

那是因为您的解决方案的时间复杂度为 O(n*n)。如果使用Map，这个问题可以通过O(n)时间复杂度解决

public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i =0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]), i};
            }else {
                map.put(nums[i], i);
            }
        }
        return new int[]{-1,-1};
    }