首页 > 代码库 > 【LeetCode】3Sum

【LeetCode】3Sum

2024-07-11 05:18:17   222人阅读

3Sum

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)

这题最naive的做法是三重循环遍历，但是O(n^3)的复杂度肯定是TLE的，即使进行优化也无效。
关键点在于将数组排序之后，就可以省掉很多重复操作。
利用“后面的元素>=前面的元素"这一点，将复杂度降为O(n^2)。
class Solution{public:    vector<vector<int> > threeSum(vector<int> &num)     {        vector<vector<int> > result;        sort(num.begin(), num.end());        for(vector<int>::size_type st1 = 0; st1 < num.size(); st1 ++)        {            //如果num[st1]==num[st1-1]，那么在num[st1-1]为首的情况下已经cover以num[st1]为首的所有情况            if(st1>0 && num[st1]==num[st1-1])                continue;            vector<int>::size_type st2 = st1+1;            vector<int>::size_type st3 = num.size()-1;            while(st2 < st3)            {                //如果num[st3]==num[st3+1]，那么在num[st3+1]为尾的情况下已经cover以num[st3]为尾的所有情况                if(st3<num.size()-1 && num[st3]==num[st3+1])                {                    st3--;                    continue;                }                int sum = num[st1]+num[st2]+num[st3];                if(sum < 0)                    st2++;                else if(sum > 0)                    st3--;                else                {                    vector<int> v;                    v.push_back(num[st1]);                    v.push_back(num[st2]);                    v.push_back(num[st3]);                    result.push_back(v);                    st2++;                    st3--;                }            }        }        return result;    }};

 































        

            
                
                  
                
                

                    联系

                    我们