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

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []Output: []

Example 3:

Input: nums = [0]Output: []

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

题意：给出一个包含 n 个整数的数组 nums ，判断 nums 是否存在三个元素 a, b, c ，使得 a + b + c = 0 。找出所有满足条件、且不重复的三元组。

思路1 排序+双指针+set去重

先排序，然后固定每个数 nums[i] ，在 nums[i+1:size()-1] 的范围内双指针搜索，寻找和为 -nums[i] 的两个元素，找到后插入集合中去重。最后返回结果：

class Solution {
   public:    vector
   
    
     > threeSum(vector
     
      & nums) {
           if (nums.size() < 3) return {
   };        set
      
       
        > ans;        sort(nums.begin(), nums.end());        for (int i = 0; i < nums.size(); ++i) {
               int x = nums[i], val = 0 - x, f = i + 1, e = nums.size() - 1;            while (f < e) {
                   if (nums[f] + nums[e] > val) --e;                else if (nums[f] + nums[e] < val) ++f;                else {
                       ans.insert({
   x, nums[f], nums[e]});                    ++f, --e;                }            }        }        vector
        
         
          > res(ans.begin(), ans.end()); return res; }};
         
        
       
      
     
    
   

效率很低：

执行用时：3084 ms, 在所有 C++ 提交中击败了5.00% 的用户内存消耗：178 MB, 在所有 C++ 提交中击败了5.00% 的用户

思路2 排序+双指针+去重优化

思考发现，如果避免使用集合去重，可以大大降低时间复杂度。我们的做法是：使用连续重复元素的第一个元素，然后在后续区间内进行双指针；得到某一个解后，跳过已经使用的解元素；双指针移动时跳过无用的重复元素。这种做法，既顾及到了可能出现重复元素的三元组如 [2, 2, -4] ，也考虑到了重复使用同一元素的问题，而且避免了多次得到重复三元组：

• 假设数 x 重复了 k 次，我们不必要执行 k 次两数之和然后去重。对于重复的数，我们只需要找到该数第一次出现的位置：

  if (i > 0 && nums[i] == nums[i-1]) continue

  就可以让我们跳过第 2, 3,..., k 次访问同一个数的情况。
• 这里的去重思路是：第一个数的三数之和的解，必然包括它之后相同的数的三数之和解。于是我们只需要得到连续重复元素序列中第一个数的解即可。

具体代码如下：

class Solution {
   public:    vector
   
    
     > threeSum(vector
     
      & nums) {
           if (nums.size() < 3) return {
   };        vector
      
       
        > ans;        sort(nums.begin(), nums.end());         for (int i = 0; i < nums.size(); ++i) {
                if (i > 0 && nums[i] == nums[i - 1]) continue; //使用连续重复元素的第一个            int newTarget = -nums[i], lo = i + 1, hi = nums.size() - 1; //三数变两数            while (lo < hi) {
                   if (nums[lo] + nums[hi] == newTarget) {
                       ans.push_back({
   nums[i], nums[lo], nums[hi]});                    while (lo < hi && nums[lo] == nums[lo + 1]) ++lo; //已经使用过的解元素                    while (lo < hi && nums[hi] == nums[hi - 1]) --hi; //已经使用过的解元素                    ++lo;                    --hi;                } else if (nums[lo] + nums[hi] < newTarget) ++lo;                else --hi;            }        }         return ans;    }};
       
      
     
    
   

效率如下：

执行用时：144 ms, 在所有 C++ 提交中击败了31.17% 的用户内存消耗：19.8 MB, 在所有 C++ 提交中击败了39.40% 的用户

更多优化如下：

• 不符合条件时，在 lo 或者 hi 移动时跳过重复元素；
• 如果当前的固定数 nums[i] 和后续数组最小的两个数 nums[i + 1], nums[i + 2] 相加，结果大于零，说明后面已经没有结果，直接退出；
• 如果当前的固定数 nums[i] 和后续数组最大的两个数 nums[size - 1], nums[size - 2] 相加，结果小于零，跳过此次双指针搜索。

class Solution {
   public:    vector
   
    
     > threeSum(vector
     
      & nums) {
           if (nums.size() < 3) return {
   };        vector
      
       
        > ans;        sort(nums.begin(), nums.end());         const int n = nums.size();        for (int i = 0; i < n - 2; ++i) {
    //只搜索到倒数第三个数为止            if (i > 0 && nums[i] == nums[i - 1]) continue; //去重剪枝,使用连续重复元素的第一个            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break; //后续循环不会有解            if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue; //本次循环不会有解            int newTarget = -nums[i], lo = i + 1, hi = nums.size() - 1; //三数变两数            while (lo < hi) {
                   if (nums[lo] + nums[hi] == newTarget) {
                       ans.push_back({
   nums[i], nums[lo], nums[hi]});                    while (lo < hi && nums[lo] == nums[lo + 1]) ++lo; //已经使用过的解元素                    while (lo < hi && nums[hi] == nums[hi - 1]) --hi; //已经使用过的解元素                    ++lo;                    --hi;                } else if (nums[lo] + nums[hi] < newTarget) {
                       while (lo < hi && nums[lo] == nums[lo + 1]) ++lo; //跳过无用的重复值                    ++lo;                }                else {
                       while (lo < hi && nums[hi] == nums[hi - 1]) --hi; //跳过无用的重复值                    --hi;                }            }        }         return ans;    }};
       
      
     
    
   

结果如下：

执行用时：112 ms, 在所有 C++ 提交中击败了62.12% 的用户内存消耗：19.8 MB, 在所有 C++ 提交中击败了34.94% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108933546 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！