LeetCode #15 – 3Sum

链接:https://leetcode.com/problems/3sum/

题目:

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:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, abc)
  • The solution set must not contain duplicate triplets.

题意:给定一些数字,求三个数相加等于0的不同组合,三个数从小到大输出

分析:先排序,枚举第一个数,然后用双指针搜索得到第二个数,注意要去处重复值

代码:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() < 3)
            return res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size()-2; ++i) {
            if(nums[i] > 0) break;
            if(i && nums[i]==nums[i-1]) continue;
            int sum = -nums[i], l = i+1, r = nums.size()-1;
            while(l < r) {
                if(l!=i+1 && nums[l]==nums[l-1]) ++l;
                else if(r!=nums.size()-1 && nums[r]==nums[r+1]) --r;
                else if(nums[l] + nums[r] < sum) ++l;
                else if(nums[l] + nums[r] > sum) --r;
                else {
                    vector<int> t = {nums[i], nums[l], nums[r]};
                    res.push_back(t);
                    ++l, --r;
                }
            }
        }
        return res;
    }
};

欢迎留言