C++版 - Leetcode 15. 3Sum 题解

[
  [-1, 0, 1],
  [-1, -1, 2]
]

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

class Solution {
    public:
        vector<vector<int> > threeSum(vector<int>& nums) {
            sort(nums.begin(), nums.end());   // 第一步是排序 
            vector<vector<int> > result;
            int len = nums.size();
            for(int i = 0; i< len; ++i) {
                int target = 0 - nums[i];  // a+b = -c
                int start = i+1, end = len-1;
                while(start < end) {
                    if(nums[start] + nums[end] == target) {
                        result.push_back({nums[i], nums[start], nums[end]});
                        start++;
                        end--;
                        while(start < end && nums[start] == nums[start-1]) start++;  // 过滤双指针扫描时的重复解: 遇到相等的数时, 跳过 
                        while(start < end && nums[end] == nums[end+1]) end--;        // 遇到相等的数时, 跳过 
                    } else if(nums[start] + nums[end] < target) {
                        start++;
                    } else {
                        end--;
                    }
                }
                if(i < len - 1) {
                    while(nums[i] == nums[i+1]) i++;   // 过滤外部扫描时的重复解: 遇到相等的数(target)时, 跳过 
                }
            }
            return result;
        }
};
// 以下为测试 
int main() {
    Solution sol;
    int arr[] = {-1, 0, 1, 2, -1, 1, 2, -4};
    vector<int> vec(arr, arr+6);
    vector<vector<int> > res = sol.threeSum(vec);
    for(auto it: res) {
        for(auto i: it) {
            cout<<i<<endl;
        }
        cout<<"----"<<endl;
    }
    return 0;
}