LeetCode15 三数之和

发表于 | 分类于 |
字数统计: 448 | 阅读时长 ≈ 2

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

题意

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0，找出所有和为 0 且不重复的三元组。

解法

除了三重循环以外，首先考虑对数组进行排序
然后二重循环得到a[i]和a[j]，对数组进行二分查找值(-a[i]-a[j])
并且要保证得到的数的下标不是i或者j，作为一组三元组的答案
但是这样有可能会得到重复的结果，所以把结果存入map进行去重，得到最后的结果
这样可以AC，但是时间和空间复杂度爆炸。

最优解是双指针
首先仍是对数组进行排序
排完序后每次遍历数组中的位置i，然后j保证大于i，k置为n-1
然后对于j和k使用双指针，根据当前的和与k的大小结果移动指针
并且每次移动的时候判断下一个数是否和之前的数相同，这样产生的结果中不会存在重复的结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 3) return {};
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        set<vector<int>> mp;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int val = -nums[i] - nums[j];
                auto r = lower_bound(nums.begin(), nums.end(), val);
                if (r == nums.end()) continue;
                int loc = r - nums.begin();
                if (nums[loc] == val) {
                    while ((loc < n) && (loc == i || loc == j)) {
                        loc++;
                    }
                    if (nums[loc] == val && loc > j)
                        mp.insert({nums[i], nums[j], nums[loc]});
                }
            }
        }
        for (auto t: mp) {
            ans.push_back(t);
        }
        return ans;
    }
};