[Leetcode] 15. 3Sum 三数之和

Related Topics：[Array][Two Pointers]
Similar Questions:[Two Sum][3Sum Closest][4Sum][3Sum Smaller]

题目：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:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
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)

思路：这道题与Leetcode[1]Two Sum相似，不同的是该题要求返回的是值而不是索引，因此可以先对数组进行排序。然后对数组元素从第一个遍历到倒数第三个，对检查到的元素之后的元素采用标准双向2Sum扫描，sum为0-当前元素值，设置两个指针，分别从剩余元素左右两端开始扫描，当指针所指元素之和小于sum，则左指针右移，当大于sum，则右指针左移。要注意跳过相同的元素，避免重复解。

java解法1：

class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> res=new LinkedList<>();
        Arrays.sort(num);
        int i=0;
        while(i<num.length-2) {
            //当与前一个元素相同时，跳过该元素的检查。
            if(i==0||(i!=0&&(num[i]!=num[i-1]))) {
                int lo=i+1;
                int hi=num.length-1;
                int sum=0-num[i];
                while(lo<hi){
                    if(num[lo]+num[hi]==sum) {
                        res.add(Arrays.asList(num[i],num[lo],num[hi]));
                        lo++;hi--;
                        //如果该元素与前（后）一元素相同，则跳过元素
                        while(lo<hi&&num[lo]==num[lo-1]) lo++;
                        while(lo<hi&&num[hi]==num[hi+1]) hi--;
                    }else if(num[lo]+num[hi]<sum) {
                        lo++;
                    }else hi--;
                }
            }
            i++;
        }
        return res;
    }
}