题解 | #数组中相加和为0的三元组#

数组中相加和为0的三元组

http://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &nums) {
        const int n = nums.size();
        if (n < 3) return {};
        
        sort(begin(nums), end(nums));
        
        vector<vector<int>> sols;
        for (int i = 0; i < n - 2; ++i) {
            if (i and nums[i] == nums[i - 1]) continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                if (nums[j] + nums[k] < -nums[i]) ++j;
                else if (nums[j] + nums[k] > -nums[i]) --k;
                else {
                    sols.push_back({nums[i], nums[j], nums[k]});
                    while (j < k and nums[j + 1] == nums[j]) ++j;
                    while (j < k and nums[k - 1] == nums[k]) --k;
                    ++j, --k;
                }
            }
        }
        
        return sols;
    }
};
全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务