15. 3Sum

给定一个数字序列，返回所有任意三个数值和为0的数值序列，其中没有重复的和为0的序列。

        首先对数字序列进行排序，如果数字序列个数小于3或者第一个数字大于0 那么返回空。 排序后的数字序列中所有小于0数字，查找它的后半部分等于-nums[indx]的二个数值，因为是排过序的，所以可以采用相向双指针，start=i+1, end=nums,size()-1. 如果存在一个nums[stary]+nums[end]==-nums[i], 那么将这{nums[i[, nums[start, nums[end]}添加到answer中。重点：为了防止插入进行相同nums[start]和nums[end]，如果nums[start]==nums[start+1]那么需要将start向后移动，如果nums[start]==nums[start-1],nums[end]向前移动。

代码

class Solution {
public:
    vector> threeSum(vector& nums) {
         sort(nums.begin(), nums.end());
        if(nums.size()<3) return {};
        if(nums[0] > 0 ) return {};
        
        vector> answer;
        
        for(int i=0; i 0) break;
            
            if(i>0 && nums[i] == nums[i-1]) continue;//重复数字 跳过
            
            int low=i+1, high=nums.size()-1;
            int sum=0;
            
            while(low < high){
                sum = nums[i] + nums[low] + nums[high];
                if(sum>0) high--;
                else if(sum < 0) low++;
                else{
                    answer.push_back({nums[i], nums[low], nums[high]});
                    //预防出现重复的数字序列
                    int last_low_occ = nums[low], last_high_cc = nums[high];
                    while(low 
2、unordered_map方法 
在排序后的数字系列中找到和为-nums[i]的二个数字，找到后，j就跳到hashmap[nums[j]]->second的下标去，同理i也需要跳转。
 
class Solution {
public:
    vector> threeSum(vector& nums) {
        sort(nums.begin(), nums.end());
        if(nums.size()<3 || nums[0]>0) return {};
        
        unordered_map hashmap;
        
        for(int i=0; i> answer;
        
        for(int i=0; i 0) break;
            
            for(int j=i+1; jsecond > j){
                    answer.push_back({nums[i], nums[j], req});
                }
                j=hashmap.find(nums[j])->second;
            }
         i = hashmap.find(nums[i])->second;
        }
       return answer;
    }
};