15. Three Sum

Three Sum

【题目】

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

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

Note:

The solution set must not contain duplicate triplets.

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

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

【分析】

乍一看这道题，最最最最直接暴力的方法是：我们可以采用对a，b，c三层for循环。但是我们提交之后时间复杂度一定会超出题目的时间限制。因为通常这种题目所给的用例会非常大，这道题暴力求解的时间复杂度是n^3，所以我们应该寻求方法，降低时间复杂度。

所以我们想到这道题目与Two Sum类似，我们可以先用a对数组进行遍历；因为题目要求是a + b + c = 0，所以这道题就变成了b + c的值等于-a，然后用之前我写过的Two Sum那道题的方法就可以了。

上面那种方法的确可以把结果跑出来，但是时间复杂度依然不是很理想，所以今天我想介绍另一种方法，这种方法我在之前的博客中也谈到过：用双向指针。

1. 首先我们要对数组进行升序排序，然后定义第一个数字a =numsindex; 对数组nums进行遍历，所以有： for (index = 0; index < nums.length; index++)
2. 其次我们需要定义两个指针，一个从左到右（我定义叫left），另一个从右到左（我定义叫right）；left = index + 1（左指针从index = 0的下一个开始）right = nums.length - 1（数组长度减一即为最后一位，index从0开始）
3. 我们有其余两个数字b和c，b = numsleft, c = numsright ，total = a + b + c，在left < right的条件下， 我们分三种情况讨论：1. total < 0;  2. total > 0; 3. total = 0
4. 第一种情况：说明三个数字中需要有一个数字变大，a是遍历整个数组，在外层，不能动；而c是从右向左移动，数组是升序排序，向左移动只能使结果越来越小，因此只能b向右移动，即：left++; 第二种情况同理，需要有数字变小，a还是不能动，b向右移动只能越来越大，所以只能c向左，即：right--； 第三种情况就是解，需要加到result中，然后左右指针同时移动到下一位即：同时进行 left++和 right--。
5. 最后我们需要对答案进行去重操作，因为题目要求是all unique。举个例子：假如一个数组{-1, -1, -1, 1, 0, -2, 2}，我们知道-1，-1，2相加是0。但是我们不知道某一个解中的-1究竟是哪个-1，所以我们应该去重。

Java实现代码如下：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int index = 0; index < nums.length; index++){
            int a = nums[index];
            if (index >= 1 && nums[index - 1] == a) {
                continue;
            }
            int left = index + 1;
            int right = nums.length - 1;
            while (left < right) {
                int b = nums[left];
                int c = nums[right];
                int total = a + b + c;
                if (total < 0) {
                    left++;
                } else if (total > 0) {
                    right--;
                } else {
                    result.add(Arrays.asList(a, b, c));  //noted
                    while (left < right && b == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && c == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}