1、两数之和

2021-05-08

两数之和

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

示例 1：

1
2
3

输入：nums = [11,2,15,7], target = 9
输出：[1,3]
解释：因为 nums[1] + nums[3] == 9 ，返回 [1, 3] 。

示例 2：

1 2	输入：nums = [3,2,4], target = 6 输出：[1,2]

示例 3：

1 2	输入：nums = [3,3], target = 6 输出：[0,1]

提示：

2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

解法一：

暴力循环。以示例1为例，我们拿到 nums 数组之后，需要为每个值循环一边 nums 数组，这样的话时间复杂度就是 O(n^2)。

public static int[] twoSum(int[] numbers, int target) {
    int[] ret = new int[2];
    for (int i = 0; i < numbers.length; i++) {
        for (int j = i + 1; j < numbers.length; j++) {
            if (numbers[i] + numbers[j] == target) {
                ret[0] = i + 1;
                ret[1] = j + 1;
            }
        }
    }
    return ret;
}

虽然这种方法可以得到解，但是在面试的时候，面试官一般会问：还有没有更优解，甚至直接给挂掉。

解法二：

使用哈希表的方式来解决，核心思想是用空间换时间。

我们在遍历的过程中，用一个 HashMap 存储数值与其对应的下标索引，然后通过 target - 当前值 的方式，得到补值然后查 HashMap 即可确定两数的下标值。

public int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; ++i) {
        if (map.containsKey(target - nums[i])) { // 检查补值是否存在
            return new int[]{map.get(target - nums[i]), i};
        }
        map.put(nums[i], i); // 补值不存在，则放入当前值
    }
    return new int[0];
}

这种解法的时间复杂度就是 O(n)，但是空间复杂度就上升到了 O(n)。

变体1

如果上述问题多加一个条件：输入的数组是一个有序数组的话，你该如何优化算法呢？

我们可以采用双指针的方式来解这道题，我们使用 i、j 两个指针，指向数组的头和尾，不断计算 num[i] 和 num[j] 的和，当和大于 target 的时候，j 前移，当和小于 target 的时候，i 后移，直至找到 i 和 j。

public int[] twoSum(int[] numbers, int target) {
    if (numbers == null || numbers.length == 0)
        return null;
    int i = 0;
    int j = numbers.length - 1;
    while (i < j) {
        int x = numbers[i] + numbers[j];
        if (x < target) {
            ++i;
        } else if (x > target) {
            j--;
        } else {
            return new int[]{i + 1, j + 1};
        }
    }
    return null;
}

三数之和

输入一个无序的数组，从这个数组中找出 3 个数之和为 0 的所有组合。
注意：要求输出不重复的解。

示例

输入：
[-1, 0, 1, 2, -1, -4],

输出：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
// [-1，-1，2]、[2, -1, -1] 这 3 个解是重复的。

解法一：

暴力解法，三层 for 循环，这里就不多说了。

解法二：

我们可以先对数组进行排序，接下来遍历数组，对于遍历到的每个值，再使用双指针的方式，查找两个与其和为 0 的值，查找一组结果就记录下来，直到遍历完成。

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (num.length < 3)
        return result;
    // sort array
    Arrays.sort(num);
    for (int i = 0; i < num.length - 2; i++) {
        if (i == 0 || num[i] > num[i - 1]) {
            int negate = -num[i];
            int start = i + 1;
            int end = num.length - 1;
            while (start < end) {
                if (num[start] + num[end] == negate) {
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[start]);
                    temp.add(num[end]);
                    result.add(temp);
                    start++;
                    end--;
                    //avoid duplicate solutions
                    while (start < end && num[end] == num[end + 1])
                        end--;
                    while (start < end && num[start] == num[start - 1])
                        start++;
                } else if (num[start] + num[end] < negate) {
                    start++;
                } else {
                    end--;
                }
            }
        }
    }
    return result;
}

本课时的文章和视频讲解，还会放到：

微信公众号：
B 站搜索：杨四正