15. 3Sum

problem description

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

algorithm thought

以之前的two sum为基础来解决这题。这里要求3个数加起来为0，也就是两个数加起来为零减去另一个数，这样就成了two sum了，首先sort一下数组，这样，之后two sum的时候能直接用左右指针逼近需求值。记得考虑如何识别一样的结果，这里题目要求不能有重复结果。

第三次做的时候，发现第二次的解答有可以优化的地方。在外层循环遍历到大于0的数的时候，就可以直接返回结果了。时间从96ms提升到了88ms。

code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        for(int i=0;i<nums.size();++i){
            if(i==0||nums[i]!=nums[i-1]){
                int left=i+1,right=nums.size()-1,sum=-nums[i];
                while(left<right){
                    if(nums[left]+nums[right]==sum){
                        vector<int> tmp;
                        tmp.push_back(nums[left]);
                        tmp.push_back(nums[right]);
                        tmp.push_back(nums[i]);
                        res.push_back(tmp);
                        while(left<right&&nums[left]==nums[left+1])
                            left++;
                        while(left<right&&nums[right]==nums[right-1])
                            right--;
                        left++;right--;
                    }
                    if(nums[left]+nums[right]<sum)
                        left++;
                    else if(nums[left]+nums[right]>sum)
                        right--;
                }
            }
        }
        return res;
    }
}; 

algorithm analysis

排序需要O(nlgn)时间复杂度，算法中有两个循环，外层循环执行n次，内层循环执行(n-i){i为0-n}次。循环需要时间复杂度是O(n平方)，最后算法的时间复杂度是O(n平方)。