3Sum

Problem: 3Sum

First we need to sort the numbers, which will do great help. Then we pick the smallest one and set two pointers to head and tail of left of the numbers. By traditional two pointers, we can quickly get results. By repeating this, we can get our answer. Also we can do some tricks to do quick return and duplicate avoidance.

Code in C++:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        std::sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++) {
            int target=nums[i];
            int head=i+1;
            int back=nums.size()-1;
            if (target>0) break;
            while(head<back) {
                int sum=target+nums[head]+nums[back];
                if (sum<0) head++;
                else if (sum>0) back--;
                else {
                    vector<int> three(3,0);
                    three[0]=nums[i];
                    three[1]=nums[head];
                    three[2]=nums[back];
                    res.push_back(three);
                    while(head<back && nums[head]==three[1]) head++;
                    while(three[2]==nums[back] && head<back) back--;
                }
            }
            while(nums[i]==nums[i+1] && i+1<nums.size()) i++;
        }
        return res;
    }
};

Code in Java:

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            int target = -nums[i];
            int l = i+1, r = nums.length-1;
            while (l < r) {
                if (nums[l]+nums[r] == target) {
                    List<Integer> triplet = new ArrayList<Integer>();
                    triplet.add(nums[i]);
                    triplet.add(nums[l]);
                    triplet.add(nums[r]);
                    res.add(triplet);
                    l++; r--;
                    while (l < nums.length && nums[l] == nums[l-1])
                        l++;
                    while (r >= 0 && nums[r] == nums[r+1])
                        r--;
                } else if (nums[l]+nums[r] < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }

        return res;
    }
}