题目如下：

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

题目大意

给定一个数组，要求找出所有和为0的三个数的集合，不能重复。

思路

最直接的思路是遍历，先对数组排序，然后第一层遍历固定第一个数字，在第一个数字右边进行第二层遍历，固定第二个数字，再进行二分查找是否有加和为0的第三个数。在此同时，为了防止重复的组合，需要记录上次和为0的值并与此次值进行比较。时间复杂度为O(n2 logn)，空间复杂度为O(1)。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public List<List<Integer>> threeSum_v2(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp;
    int lastIndex_i = -1, lastIndex_j = -1;
    for (int i = 0; i < nums.length - 2;) {
        for (int j = i + 1; j < nums.length - 1; j++) {
            int position = binarySearch(nums, - (nums[i] + nums[j]), j + 1, nums.length);
            if (position != -1) {
                if (!(lastIndex_i != -1 && nums[i] == nums[lastIndex_i] && nums[j] == nums[lastIndex_j])) {
                    temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[j]);
                    temp.add(nums[position]);             
                    result.add(temp);
                    lastIndex_i = i;
                    lastIndex_j = j;
                }
            }
        }
        i++;
        while (i < nums.length - 2 && nums[i] == nums[i - 1]) {
            i++;
        }
    }
    return result;
}

private int binarySearch(int [] nums, int target, int lo, int hi){
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > target) {
            hi = mid;
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

提交之后AC了，但是时间惨不忍睹，218ms。

运行时间
运行时间

看了看大神们是怎么做的，思路和我很类似，也是先对数组排序，但是在第二层遍历的时候直接进行第二和第三个数字。对于每一个第一层的数字，第二层遍历分别将最左端的值和最右端的值最为初始值,left和right，如果加和发现过大，那么就是右边的值太大，将right减1。反之如果加和发现太小，那么就是左边的值太小，将left加1，以此类推，直至三个数加和或者left大于right。仍需要注意的是，在第二层遍历中，如果找出了一组加和为0的集合，记录之后如果left右边或者right左边有与left和right相同的值，则分别需要进行左移和右移防止集合重复。

这个算法还有其他小细节的改进。如果发现第一个数字为正数，那么可以直接结束搜索，因为正数右边全为正数，加和不可能为0。其次，如果排序之后发现最后一个数为负数，那么也可以直接结束搜索。此算法进行了两层循环，所以时间复杂度为O(n2)，空间复杂度为O(1)。代码如下

​```Java
public List<List> threeSum_v1(int[] nums) {
List<List> lists = new ArrayList<>();
Arrays.sort(nums);
if (nums.length > 0 && nums[nums.length - 1] < 0) return lists;
for (int i = 0; i < nums.length - 2; i++) {

    // if nums[i] > 0, we can never get sum to 0
    if (nums[i] > 0) break;
    
    //avoid duplicate triplets
    if (i != 0 && nums[i] == nums[i - 1]) continue;
    
    int target = -nums[i];
    int left = i + 1, right = nums.length - 1;
    // both side
    while (left < right) {
        // target is negative
        if (nums[left] + nums[right] > target) {
            // right side is too huge
            right--;
        } else if (nums[left] + nums[right] < target) {
            // left side is too small
            left++;
        } else {
            lists.add(Arrays.asList(nums[i], nums[left], nums[right]));
            // avoid duplicate 
            while (++left < right && nums[left] == nums[left - 1]) ;
            while (--right > left && nums[right] == nums[reft + 1]) ;
        }
    }
}
return lists;

}


提交结果，运行时间为71ms：

{% image time_2.jpg '运行结果' '' %}

### 总结

第二版的运行时间比我的第一版短了2/3，而且代码比我的清晰简洁了很多。算法的能量是巨大的，仍需继续努力啊。