leetcode 15. 三数之和

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res; 
    sort(nums.begin(),nums.end());
    for(int i = 0; i + 2 < nums.size() ; ++i)       //注意如果是i < nums.size()-2,数组为空时会发生下溢
    {
        if(nums[i] > 0) break;      //后面的数字均大于0，故不存在符合条件的结果
        if(i > 0 && nums[i] == nums[i-1])   continue;       //以nums[i-1]开头的3个数的组合已经判断过

        int target = - nums[i];
        int l = i + 1, r = nums.size() - 1;
        while(l < r)
        {
            int sum = nums[l] + nums[r];
            if(sum == target)
            {
                res.push_back({nums[i],nums[l],nums[r]});
                l++;
                r--;
                while(l < r && nums[l] == nums[l-1])    l++;
                while(l < r && nums[r] == nums[r+1])    r--;
            }
            if(sum < target)  l++;
            if(sum > target)  r--;
        }
    }
    return res;
    }
};