Leetcode日记：15&16.三数之和

题目15：三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

1
2
3
4
5
6
7
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析

这道题让我们求三数之和，比之前那道Two Sum要复杂一些，博主考虑过先fix一个数，然后另外两个数使用Two Sum那种HashMap的解法，但是会有重复结果出现，就算使用set来去除重复也不行，会TLE，看来此题并不是考我们Two Sum的解法。那么我们来分析一下这道题的特点，要我们找出三个数且和为0，那么除了三个数全是0的情况之外，肯定会有负数和正数，我们还是要先fix一个数，然后去找另外两个数，我们只要找到两个数且和为第一个fix数的相反数就行了，既然另外两个数不能使用Two Sum的那种解法来找，如果能更有效的定位呢？我们肯定不希望遍历所有两个数的组合吧，所以如果数组是有序的，那么我们就可以用双指针以线性时间复杂度来遍历所有满足题意的两个数组合。

我们对原数组进行排序，然后开始遍历排序后的数组，这里注意不是遍历到最后一个停止，而是到倒数第三个就可以了。这里我们可以先做个剪枝优化，就是当遍历到正数的时候就break，为啥呢，因为我们的数组现在是有序的了，如果第一个要fix的数就是正数了，那么后面的数字就都是正数，就永远不会出现和为0的情况了。然后我们还要加上重复就跳过的处理，处理方法是从第二个数开始，如果和前面的数字相等，就跳过，因为我们不想把相同的数字fix两次。对于遍历到的数，用0减去这个fix的数得到一个target，然后只需要再之后找到两个数之和等于target即可。我们用两个指针分别指向fix数字之后开始的数组首尾两个数，如果两个数和正好为target，则将这两个数和fix的数一起存入结果中。然后就是跳过重复数字的步骤了，两个指针都需要检测重复数字。如果两数之和小于target，则我们将左边那个指针i右移一位，使得指向的数字增大一些。同理，如果两数之和大于target，则我们将右边那个指针j左移一位，使得指向的数字减小一些，代码如下：

15代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new LinkedList<>();
    for (int i = 0; i < nums.length-2; i++) {
        if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {//防止重复元素计入
            int lo = i+1, hi = nums.length-1, sum = 0 - nums[i];
            while (lo < hi) {
                if (nums[lo] + nums[hi] == sum) {
                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while (lo < hi && nums[lo] == nums[lo+1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi-1]) hi--;
                    lo++; hi--;
                } else if (nums[lo] + nums[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}

题目16：最接近的三数之和

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

1
2
3
Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

类似的思想

类似于3求和问题，使用3个指针指向当前元素、下一个元素和最后一个元素。如果总和小于目标值，这意味着我们必须添加一个更大的元素，这样下一个元素就会移到下一个。如果总和更大，这意味着我们必须添加一个更小的元素，所以最后一个元素移到第二个最后一个元素。一直坚持到最后。每次比较总和和目标之间的差异，如果到目前为止它小于最小差异，那么用它替换结果，否则继续迭代。

16代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int threeSumClosest(int[] num, int target) {
    int result = num[0] + num[1] + num[num.length - 1];
    Arrays.sort(num);
    for (int i = 0; i < num.length - 2; i++) {
        int start = i + 1, end = num.length - 1;
        while (start < end) {
            int sum = num[i] + num[start] + num[end];
            if (sum > target) {
                end--;//最后一个元素向前移动一位
            } else {
                start++;//下一个元素向后移动
            }
            if (Math.abs(sum - target) < Math.abs(result - target)) {
                result = sum;
            }
        }
    }
    return result;
}

个人总结

当涉及到给定乱序数组，要求在其中按照要求找到所需内容时，我们先想排序能不能简化问题，如果能，我们选用库自带函数sort()，这道题一开始我尝试用最暴力的解法，但是O(N^3)的时间复杂度实在是太高了，会TLE，那么我们能不能同时引导两个指针的移动呢，但是可以的，这样虽然只会线性增长，不会指数增长。

核心思想，一个数组，三个指针，一个从第一个开始可以称之为根（root），移动到最后（倒数第三个），另外两个，一个指向最大元素（end），另一个指向第一个指针的后面的元素（start）