wangjie_fourth

may the force be with you

0%

俩数之和

发表于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟

题目

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。

Coding

题目分析

这道题目就是从一个数组中找到俩个数之和跟目标值相等即可。

  • nums数组、target会不会为null？不会，这都是基本数据类型，那就不需要考虑null
  • 数组是不是有序的？没说，那就是无序的。这个是要经常考虑到的
  • 数组元素会不会重复？没说，那就是可能重复
  • 数组个数会不会小于2，小于2怎么办？直接抛异常吧
  • nums数组元素可以复用吗？不可以复用，题目说了
  • 输出值的顺序有要求吗？没有要求，题目说了
  • 数组中会有多组符合条件的数据吗？不会，题目说了
  • 如果找不到符合条件的值，应该返回什么？题目没说，这里就抛出异常吧

写测试用例

示例 1： 

1
2
输入：nums = [2,7,11,15], target = 9
输出：[0,1] 或者 [1,0]

示例 2： 

1
2
输入：nums = [2,2], target = 4
输出：[0,1] 或者 [1,0]

示例 3：

1
2
输入：nums = [2,3,4], target = 9
输出：抛出异常

思路分析

暴力思路

这种题目循环遍历俩次数组，依次拿数组中的一个元素去与其他元素相比较。直至找到合适的那一个，没有就找下一个，一直到数组的最后一个。要是找不到，就抛出异常。

HashMap优化

这道题的O(n^2)原因就是因为需要二次遍历数组。如果第二次在寻找指定值可以常数时间的话，那么就大大缩短时间复杂度。这也就是哈希表的应用之处。
在寻找target - nums[i]时，直接到哈希表去找，他的查找时间是O(1)。
但是这里需要考虑key重复的问题，理论上出现重复的key就会覆盖上一个元素的值，所以需要要想办法让这个key唯一，比如说：nums[i]+i，即20+2。这样理论上，key就不会重复了。

但好像不行，这个key的i没法确定，有重复元素就GG

但是，这里还有一个巧妙的技巧。可以把数组在遍历的时候，依次放入哈希表中。让后面的元素再去匹配这个哈希表。

这个思路还是不太能理解，不知道是不是其他什么技巧

代码实现

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i<nums.length; i++ ) {
            int a1 = nums[i];
            for (int j=0; j<nums.length; j++) {
                int a2 = nums[j];
                if (j == i) {
                    continue;
                } else if (a1 + a2 == target) {
                    return new int[]{i,j};
                }
            }
        }
        throw new RuntimeException("该数组不存在target的俩个值");
    }
}

暴力解法好像没啥说的，只要注意第二次遍历需要避免使用相同的元素。但是看了别人的答案，才知道自己的解法多么暴力。
想想自己的解法，假设所有可能答案的总数是m条，那我就用2m条去试答案。举个例子，你试了[1,2]这个答案，那么我还会试[2,1]这个答案。因为题目说了，不需要考虑顺序，所以这里是一个优化点。
而且如果第二次遍历永远不会涉及到num[i]的话，那么去比较i == j就是没有意义的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i<nums.length; i++ ) {
            int a1 = nums[i];
            for (int j=i+1; j<nums.length; j++) {
                int a2 = nums[j];
                if (a1 + a2 == target) {
                    return new int[]{i,j};
                }
            }
        }
        throw new RuntimeException("该数组不存在target的俩个值");
    }
}

这里如果在分析题目的时候，画一个正方形好像就容易考虑到这个问题了

时间复杂度：= n-1 + n-2 + … + 1 = (n-1)(n-1 + 1)/2 = O(n^2)
空间复杂度：= O(n)

使用哈希表优化

之前的暴力解法是因为第二次查找target - num[i]需要去遍历数组，第一次遍历肯定是无法避免的，问题是怎么去避免第二次遍历？这里就是使用哈希表来将O(n)降成O(1)。大概思路是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 将nums存在这个hashMap，后面去获取
        Map<Integer, Integer> numsMap = new HashMap<>();
        for (int i = 0; i<nums.length; i++ ) {
            numsMap.put(nums[i], i);
        }

        for (int i = 0; i<nums.length; i++ ) {
            int a1 = nums[i];

            // 看hashMap有没有
            if (numsMap.containsKey(target - nums[i])) {
                if (numsMap.get(target - nums[i]) == i) {
                    continue;
                }
                return new int[]{numsMap.get(target - nums[i]), i};
            }
        }
        throw new RuntimeException("该数组不存在target的俩个值");
    }
}

这个时候你仔细分析一下这个算法的时间复杂度是O(2n)，虽然是改善了点，但是有一个重要的问题没解决。如果nums数组含有多个相同元素的话，那哈希表就崩了。

我也是在这个时候，感觉要去重写一个符合自己要求的哈希表，否则现在是解决不了这个问题的

然后，看一下标准答案的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums.length < 2) {
            throw new RuntimeException("nums数组大小不能低于2");
        }
        // 将nums存在这个hashMap，后面去获取
        Map<Integer, Integer> numsMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int a1 = nums[i];

            // 看hashMap有没有
            if (numsMap.containsKey(target - nums[i])) {
                return new int[]{numsMap.get(target - nums[i]), i};
            }
            numsMap.put(nums[i], i);
        }
        throw new RuntimeException("该数组不存在target的俩个值");
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

如果只让算出数值，不要求下标

这个题目有一个变形，就是只要求获取数值，不要求下标。这时候可以考虑双指针思路

双指针思路

因为题目只需要数值，不在乎下标，这种情况就可以考虑先排一下序，然后再去寻找。

比如说：数组为[1, 4, 20, 15, 8, 6, 3]，target为10时。在第一次循环时，1 + 20 > 10。那么后续比1大的数字理论上就没必要去运算了。
所以，这个时候如果我们把数组先排个序，后面就没必要进行O(n^2)的操作。

这种思路也叫做双指针解法，很常用

现在思路就是：先将这个数组排序，然后用一个指针指向最小值，一个指针指向最大值。接着用俩个指针指向的值相加，如果大于目标值，就把最大值那个指针往下移；如果小于目标值，就把最小值那个指针往上移。

双指针思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums.length < 2) {
            throw new RuntimeException("nums数组大小不能低于2");
        }
        Arrays.sort(nums);
        int lower = 0;
        int high = nums.length - 1;

        while (lower <= high){
            int nowNum = nums[lower] + nums[high];
            if (nowNum > target) {
                --high;
            } else if (nowNum < target) {
                ++lower;
            } else {
                return new int[]{nums[lower], nums[high]};
            }
        }
        throw new RuntimeException("该数组不存在target的俩个值");
    }
}