3Sum

Id.15. 3Sum Add to List QuestionEditorial Solution My Submissions
Total Accepted: 165869
Total Submissions: 802806
Difficulty: Medium
Contributors: Admin
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: 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]
]

这道题目因为需要去重和遍历，所以用传统的方法遍历会出现很多的重复步骤，因为这个题目不要重复值，所以我们可以对其先进行排序，双指针在有序的数列问题中表现很好，所以使用双指针算法。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.size()<2)
        return result;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++)
        {  
            if ((i>0)&&nums[i]==nums[i-1]) continue;
          int left=i+1;
          int right=nums.size()-1;
          while(left<right)

          {  
              if((nums[left]+nums[right])==(-1*nums[i]))
                { vector<int> vec;
                vec.push_back(nums[i]);
                vec.push_back(nums[left]);
                vec.push_back(nums[right]);
                result.push_back(vec);
                left++;
                right--;
                while(nums[left]==nums[left-1]) left++;

                while(nums[right]==nums[right+1]) right--;
                }
                else if((nums[left]+nums[right])<(-1*nums[i]))
                    left++;
                else  right--;


          }
        }
        return result;

    }
};
`

该算法的核心，因为首先进行了排序，所以可以方便的使用双指针，如果小于一个目标值则进行left+1,大于则right-1.
关键步骤是去重。因为对于排序过后的数组，这三个数如果和在向下一步走的时候，如何和上一步相等则即可判断为重复。