首页 > 代码库 > 3Sum

3Sum

2024-07-29 06:29:01   220人阅读

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)

 

思路：先对数组排序，之后三个变量i(0->num.size()-1),j(initial:i+1),k(initial:num.size()-1)，i 扫描数组，判定sum=(num[i]+num[j]+num[k]==0) ? OK:(sum>0 ? --k:++j)；

问题的关键在于细节的考虑，若去处一下程序中的三个if判断，则对于上述example，（-1，-1,2）将有两个输出，判断在于对重复情况的去除

code:

class Solution {public:    vector<vector<int> > threeSum(vector<int> &num) {        vector<vector<int> >result;        if(num.size()<3)            return result;                sort(num.begin(),num.end());                int sum=0;        vector<int>tmp;        for(int i=0;i<num.size();++i)        {            if(i>0&&num[i]==num[i-1])                continue;                            int j=i+1;            int k=num.size()-1;            while(j<k)            {                if(j>i+1&&num[j]==num[j-1])                {                    ++j;                    continue;                }                                    if(k<num.size()-1&&num[k]==num[k+1])                {                    --k;                    continue;                }                                sum=num[i]+num[j]+num[k];                if(sum<0)                    ++j;                else if(sum>0)                    --k;                else                {                    tmp.push_back(num[i]);                    tmp.push_back(num[j]);                    tmp.push_back(num[k]);                    result.push_back(tmp);                    tmp.clear();                    ++j;                    --k;                }            }        }                return result;    }};
View Code

也可以使用STL中相关函数解决上面问题

prev:

template <class BidirectionalIterator>  BidirectionalIterator prev (BidirectionalIterator it,       typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
Get iterator to previous element. Returns an iterator pointing to the element that it would be pointing to if advanced -n positions.

If it is a random-access iterator, the function uses just once operator+ or operator-. Otherwise, the function uses repeatedly the increase or decrease operator (operator++ or operator--) on the copied iterator until n elements have been advanced.

upper_bound(first,last,x):返回值是寻找到元素下一位置的迭代器；

code:

class Solution {public:    vector<vector<int> > threeSum(vector<int> &num) {        vector<vector<int> >result;        if(num.size()<3)            return result;                sort(num.begin(),num.end());                auto last=num.end();        for(auto a=num.begin();a<prev(last);a=upper_bound(a,prev(last),*a))        {            for(auto b=next(a);b<prev(last);b=upper_bound(b,prev(last),*b))            {                const int c=-(*a+*b);                if(binary_search(next(b),last,c))                    result.push_back(vector<int> {*a,*b,c});            }        }                return result;    }};
View Code

 

3Sum


联系
我们