剑指 Offer II 007. 数组中和为 0 的三个数

leetcode力扣刷题打卡

题目:剑指 Offer II 007. 数组中和为 0 的三个数
描述:给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a ,b ,c ,使得 a + b + c = 0 ?请找出所有和为 0 且 不重复 的三元组。

思路:

1、先排序,然后用双指针找到目标值,用set去重。

原代码##

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return {};
        sort(nums.begin(), nums.end());
        if (nums[0] > 0) return {};
        set<vector<int>> s;
        for (int i = 1; i < n - 1; ++i) {
            int l = 0, r = n - 1;
            while (l < i && r > i) {
                int temp = nums[l] + nums[i] + nums[r];
                if (temp < 0) l++;
                else if (temp > 0) r--;
                else {
                    s.insert({nums[l], nums[i], nums[r]});
                    l++;
                    r--;
                }
            }
        }
        vector<vector<int>> ans(s.begin(), s.end());
        return ans;
    }
};

你可能感兴趣的