【LeetCode】16.3Sum

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)
刚看到本题，想法是先任意取两个数加和sum2，再在数组中查看是否有0-sum2存在。如果存在则添加到结果集中。但这样做不如倒过来，从头遍历，取一个数，然后找后面的数中有没有两个加和sum2等于这个数的相反数。有利于问题有化简。那么问题就变成之前做过的2sum的问题了。2sum可以从O(n2)优化到O(n)。
用 2sum 的第三种方法（带HASHMAP的）会出现Output Limit Exceeded ，
用第二处方法不去重也会出现Output Limit Exceeded.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < num.length; i++) {
            if (i > 0 && num[i] == num[i-1]) continue;
            int sum = 0 - num[i];
            ArrayList<Pair> pairs = getSum(num, sum, i + 1);
            for (int j = 0; j < pairs.size(); j++)
            {
                Pair pair = pairs.get(j);
                ArrayList<Integer> arr = new ArrayList<Integer>();
                arr.add(num[i]);
                arr.add(pair.x);
                arr.add(pair.y);
                ans.add(arr);
            }
        }
        return ans;
    }
     
    public ArrayList<Pair> getSum(int[] tmp, int target, int left) {
        ArrayList<Pair> ans = new ArrayList<Pair>();
        int l = left;
        int r = tmp.length - 1;
        while(l< r){
            int sum = tmp[l] + tmp[r];
            if(sum == target){
                Pair p = new Pair();
                p.x = tmp[l];
                p.y = tmp[r];
                ans.add(p);
                while (l+1 < tmp.length && tmp[l] == tmp[l+1]) {
                    l++;
                }
                while (r - 1 >= 0 && tmp[r] == tmp[r - 1]) {
                    r--;
                }
                r--;
                l++;
            }else if (sum > target){
                    r--;
            }else{
                    l++;
            }
            
        }
        return ans;
    }
}
 
class Pair
{
    public int x;
    public int y;
}