本文共 2268 字，大约阅读时间需要 7 分钟。

题目

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 
   
    class Solution {public:    vector
    
     
      > threeSum(vector
      
       & nums) {        vector
       
        
         > 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 
   
    class Solution {public:    vector
    
     
      > threeSum(vector
      
       & nums) {        vector
       
        
         > 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; }};
        
       
      
     
    
   

转载地址：http://aibmb.baihongyu.com/