[数据结构与算法]三数之和【leetcode 15】

简单一句话，先排序，然后固定第一个数a，再然后b、c只能从两边向中间靠（在a之后）。细节条件就是去重处理（i，L，R三个索引的去重都要考虑）

解答

1、官方代码：

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        if (nums.size()<3) return {}; // 特判

        sort(nums.begin(),nums.end()); // O(nlogn)

        vector<vector<int>> result;
        for (size_t i = 0; i < nums.size(); i++)
        {
            if(nums[i]>0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了

            if(i>0&&nums[i]==nums[i-1]) continue; // 去掉重复情况

            int left = i+1;
            int right = nums.size()-1;

            //双指针逻辑
            while (left<right)
            {
                int sum = nums[i]+nums[left]+nums[right];
                if (sum==0)
                {
                    result.push_back({nums[i],nums[left],nums[right]});  
                    left++;
                    right--;
                    // 去重：第二个数和第三个数也不重复选取
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
                else if(sum>0)
                {
                    right--;
                }
                else
                {
                    left++;
                }                
            }            
        }
        return result;
    }
};

2、我的去重解法：

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        if (nums.size()<3) return {}; // 特判

        sort(nums.begin(),nums.end()); // O(nlogn)

        vector<vector<int>> result;
        for (size_t i = 0; i < nums.size(); i++)
        {
            if(nums[i]>0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了

            if(i>0&&nums[i]==nums[i-1]) continue; // 去掉重复情况

            int left = i+1;
            int right = nums.size()-1;

            //双指针逻辑
            while (left<right)
            {
                //过滤掉left重复值
                if(left>i+1&&nums[left]==nums[left-1])
                {
                    left++;
                    continue;
                }

                //过滤掉right重复值
                if(right<nums.size()-1&&nums[right]==nums[right+1])
                {
                    right--;
                    continue;
                }

                int sum = nums[i]+nums[left]+nums[right];
                if (sum==0)
                {
                    result.push_back({nums[i],nums[left],nums[right]});  
                    left++;
                    right--;
                }
                else if(sum>0)
                {
                    right--;
                }
                else
                {
                    left++;
                }                
            }            
        }
        return result;
    }
};