题解 | #三数之和#

改进：数组排序+双指针，判断num[i]+num[l]+num[r]==0

• num数组升序排序；

• 遍历到倒数第3个元素num[i]；l=i+1; r=num.length-1；

  • 特殊判断：if(num[i]>0)，后边不可能有和等于0，break；

  • num[i]与num[i-1]比较去重；（使用HashMap）

  • if(num[i]+num[l]+num[r]==0)，保存{num[i], num[l], num[r]};

    • 循环比较num[l+1], num[r-1]与num[l], num[r]去重；

  • elif(num[i]+num[l]+num[r]>0)，r-1; (r-1才可能让值变小，同时排除了l+1,l+2,...与r的组合)

  • elif(num[i]+num[l]+num[r]<0)，l+1; (同理)

  • 直到 l >= r；

注意：

• 标粗代码是方法的骨架，而去重、特殊判断实际是剪枝操作；

• 比较两数的大小关系，用到排序+双指针；

• 当前元素与前边的元素比较，先保存前边的元素，可用到HashMap；

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  //用来去重
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    Arrays.sort(num);
    for(int i=0;i<num.length-2;i++){  //遍历到倒数第三个元素
        if(num[i]>0) break;
        if(map.containsKey(num[i])) continue; //如果前边已经组合过该元素，去重
        else map.put(num[i],i);
        int l = i +1, r = num.length-1;
        while(l<r){
            if(num[i]+num[l]+num[r]==0){
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(num[i]);
                list.add(num[l]);
                list.add(num[r]);
                res.add(list);
                int preLNum = num[l], preRNum = num[r];
                while (++l<--r){  //去重
                    if(preLNum==num[l] && preRNum==num[r]){
                        preLNum = num[l];
                        preRNum = num[r];
                    }else break;
                }
            }else{
                if(num[i]+num[l]+num[r]>0) --r;
                else ++l;
            }
        }
    }
    return res;
}