算法 15. 三数之和

LeetCode https://leetcode.cn/problems/3sum/

题目描述

给你一个整数数组nums，判断是否存在三元组nums[i], nums[j], nums[k] 满足 i!=j && i!=k && j!=k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

思路

类似与两数之和, 双指针操作

代码

typedef std::vector<std::vector<int>> array2d;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        array2d result;
        sort(nums.begin(), nums.end());
        auto size = nums.size();
        for (auto i = 0; i < size - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            auto j = i + 1;
            auto k = size - 1;
            while (j < k) {
                auto & v1 = nums[i];
                auto & v2 = nums[j];
                auto & v3 = nums[k];
                auto sum = v1 + v2 + v3;
                if (0 == sum) {
                    result.push_back({v1, v2, v3});
                    j++;
                    k--;
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                } else if (0 > sum) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return result;
    }
};