首页 > 代码库 > [C++]LeetCode: 70 3Sum

[C++]LeetCode: 70 3Sum

题目:

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

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • 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)

思路:

本题的解法类似于LeetCode: 15 3Sum Closest (plus JAVA Code).也是使用先排序,后夹逼的方法求解答案。

不同的地方在于,我们需要根据第一个元素的移动(改变),不断确定新的target, 即twosum.

同时我们需要考虑如何跳过重复的集合,移动夹逼的两个左右指针时,需要进行判断移动前后元素是否相等,重复则skip。

Attention:

1. 为了不改变原来的数组,我将数组存在ivec中,再进行排序和后续操作。

//不想改变原数组,所以存在ivec中
        vector<int> ivec(num.begin(), num.end());
        
        if(num.size() < 3) return ret;
        
        sort(ivec.begin(), ivec.end());
2. 在外层大的循环下,我们不设置i++, 在循环体内判断,如果有重复数字,不断跳过。

for(int i = 0; i < ivec.size() - 2; )

//如果之间有重复的,就一直跳过
            do{
                i++;
            }while(i < ivec.size() - 1 && ivec[i-1] == ivec[i]);
3. 进行循环后,每次都需要计算 num[i]的相反数,作为target来匹配。可能存在多个匹配情况,所以即使一次匹配成功,仍然需要改变夹逼指针j 和 k,寻找其他可能的匹配组合。

int twosum = 0 - ivec[i]; //把-num[i]作为target去寻找匹配的两个数
            
while(j < k)
{
//即使找到第一个匹配的项,仍然需要移动坐标,寻找其他可能匹配数
   if(ivec[j] + ivec[k] == twosum)
   {
     vector<int> tmp{ivec[i], ivec[j], ivec[k]};
     ret.push_back(tmp);
     do{
         j++;
     }while(j < k && ivec[j] == ivec[j-1]);
     do{
          k--;
     }while(j < k && ivec[k] == ivec[k+1]);
    }
复杂度: O(N^2)

AC Code:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> ret;
        //不想改变原数组,所以存在ivec中
        vector<int> ivec(num.begin(), num.end());
        
        if(num.size() < 3) return ret;
        
        sort(ivec.begin(), ivec.end());
        
        for(int i = 0; i < ivec.size() - 2; )
        {
            int j = i + 1;
            int k = ivec.size() - 1;
            int twosum = 0 - ivec[i]; //把-num[i]作为target去寻找匹配的两个数
            
            while(j < k)
            {
                //即使找到第一个匹配的项,仍然需要移动坐标,寻找其他可能匹配数
                if(ivec[j] + ivec[k] == twosum)
                {
                    vector<int> tmp{ivec[i], ivec[j], ivec[k]};
                    ret.push_back(tmp);
                    do{
                        j++;
                    }while(j < k && ivec[j] == ivec[j-1]);
                    do{
                        k--;
                    }while(j < k && ivec[k] == ivec[k+1]);
                }
                else if(ivec[j] + ivec[k] < twosum)
                    j++;
                else
                    k--;
            }
            
            //如果之间有重复的,就一直跳过
            do{
                i++;
            }while(i < ivec.size() - 1 && ivec[i-1] == ivec[i]);
        }
        
        return ret;
    }
};

这道题其实还可以嵌套一个twosum子程序来做。其他博文中有给出。3Sum

重点是,我们一定要注意细节的处理,就是夹逼指针的移动。

[C++]LeetCode: 70 3Sum