LeetCode之ThreeSum

拼搏现实的明天。 2022-08-05 02:14 40阅读 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:  
• 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)  
  
分析：暴力求解时间复杂度为O(n3)，效率太低，不考虑，这里使用2sum中的第三种方法。先排序然后左右夹逼，类似二分查找  
  
的思想。  
  
代码：

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    class Solution{
    public:
        vector<vector<int>> threeSum(vector<int>& num) {
            vector<vector<int>> result;
            vector<int> temp(3);
            if (num.size() < 3) return result;
            sort(num.begin(),num.end());
            const int target =0;
            auto last = num.end();//在C++11标准的语法中，auto被定义为自动推断变量的类型。
    
            cout << *(last-1) << *num.begin();
            for (auto i = num.begin(); i < last-2; ++i) {
                auto j = i+1;
                if (i > num.begin() && *i == *(i-1)) continue;//排除，相同数字的情况
                auto k = last-1;
                while (j < k) {
                    if (*i + *j + *k < target) {
                        ++j;
                        while(*j == *(j - 1) && j < k) ++j;//排除，相同数字的情况
                    } else if (*i + *j + *k > target) {
                        --k;
                        while(*k == *(k + 1) && j < k) --k;//排除，相同数字的情况
                    } else {
                        temp[0] = *i;
                        temp[1] = *j;
                        temp[2] = *k;
                        result.push_back(temp);
                        ++j;
                        --k;
                        while(*j == *(j - 1) && *k == *(k + 1) && j < k) --k;//或++j
                    }
                }
            }
            return result;
    
        }
    };
    
    int _tmain(int argc, _TCHAR* argv[])
    {
        vector<int> v1;
        vector<vector<int>> v2;
    
        v1.push_back(-1);
        v1.push_back(0);
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(-1);
        v1.push_back(-4);
    
        Solution s;
        v2 = s.threeSum(v1);
        vector<vector<int>>::iterator v2_Iter;
        vector <int>::iterator v1_Iter;
        for ( v2_Iter = v2.begin( ) ; v2_Iter != v2.end( ) ; v2_Iter++ ){
            cout << "v2 =" ;
            for(v1_Iter = (*v2_Iter).begin();v1_Iter != (*v2_Iter).end();v1_Iter++){
                cout << " " << *v1_Iter;
            }
                cout << endl;
            }
    
        system("pause");
        return 0;
    }

总结：像这种可以排序而没有排序的数组，我们可以先排序，然后再操作，这样可以降低时间复杂度，对于有序的数组我们永  
  
远第一想法就是二分查找的这种夹逼的思想。  
如果每个数字对应有其他一些信息，使用hash是个不错做法。