3Sum

灰太狼 2022-06-07 13:16 152阅读 0赞

# 题目 #

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:** The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],
    
    A solution set is:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

# 分析 #

给出n个整数，a, b, c为数组中的三个元素，求出所有满足a + b + c = 0的三元组。

对于这道题，最容易想到的求解方法就是用三层循环对数组进行遍历，求解出满足题意的所有三元组。

代码如下：

#include <algorithm>
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> result;
            if (nums.size() < 3) {
                return result;
            }
            sort(nums.begin(), nums.end());
            for (int i = 0; i < nums.size() - 2; i++) {
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                for (int j = i + 1; j < nums.size() - 1; j++) {
                    if (j > i + 1 && nums[j] == nums[j - 1]) {
                        continue;
                    }
                    for (int k = j + 1; k < nums.size(); k++) {
                        if (k > j + 1 && nums[k] == nums[k - 1]) {
                            continue;
                        }
                        if (nums[i] + nums[j] + nums[k] == 0) {
                            result.push_back({nums[i], nums[j], nums[k]});
                        }
                    }
                }
            }
            return result;
        }
    };

但是，该方法的时间复杂度过高，提交的代码超时。因此，需要使用时间复杂度更低的方法。

我们可以先确定第一个元素的值，然后通过移动其他两个元素来寻找符合要求的三元组。

假如a <= b <= c，且数组已经排好序。a, b, c在数组中的索引分别为i, j, k，数组长度为n。

先假设索引 i 对应的值符合要求, 然后j = i + 1, k = n - 1。

令 sum = a + b +c。

若 sum == 0，符合要求，记录该三元组，然后 i++，进行下一轮循环。

若 sum > 0，说明三个值的和过大，因此 k--。

若 sum < 0，说明三个值的和过小，因此 j++。

当 j >= k 时，说明此时a的值不符合要求，需要重新确定 a 的值。i++，进入下一轮循环。

需要注意的是，当a（或者b或者c）与前一个a（或者b或者c）的值相同时（给出的数组有可能有相同的元素），跳过该值。

代码如下：

#include <algorithm>
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> result;
            if (nums.size() < 3) {
                return result;
            }
            sort(nums.begin(), nums.end());
            int i, j, k;
            for (i = 0; i < nums.size() - 2 && nums[i] <= 0; i++) {
                while (i > 0 && nums[i] == nums[i - 1]) {
                    i++;
                }
                if (i >= nums.size() - 2 || nums[i] > 0) {
                    break;
                }
                for (j = i + 1, k = nums.size() - 1; j < k;) {
                    while (j > i + 1 && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (k > nums.size() && nums[k] == nums[k + 1]) {
                        k--;
                    }
                    if (j >= k) {
                        break;
                    }
                    int temp = nums[i] + nums[j] + nums[k];
                    if (temp == 0) {
                        result.push_back({nums[i], nums[j], 0- nums[i] - nums[j]});
                        j++;
                        k--;
                    } else if (temp < 0) {
                        j++;
                    } else {
                        k--;
                    }
                }
            }
            return result;
        }
    };