首页 > 代码库 > leetcode -- 3sum

leetcode -- 3sum

2024-07-06 05:14:10   224人阅读

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)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
    vector<vector<int> > ret;
public:
    void helper(vector<int> &num,vector<int>::size_type  base)
    {
      vector<int>::size_type  left = base + 1;
      vector<int>::size_type  right = num.size() - 1;
      int com = num[base] * (-1);

      while(left < right)
      {
        int temp = num[left] + num[right];
        if( temp > com )
            right--;
        else if(temp < com)
            left++;
        else
            {
              vector<int> t;
              t.push_back(num[base]);t.push_back(num[left]);t.push_back(num[right]);
              ret.push_back(t);
              right--;left++;
            }
      }
    
    }
    vector<vector<int> > threeSum(vector<int> &num) {
        sort(num.begin(),num.end()); ///进行排序，运用迭代器～
        for(vector<int>::size_type i = 0;i< num.size();i++)
            if(i > 0 && num[i] == num[i -1])
             continue;
            else 
             helper(num,i);
        return ret; 
    }
};

int main()
{
  vector<int > t;
  t.push_back(-1);t.push_back(0);t.push_back(1);t.push_back(2);t.push_back(-1);t.push_back(-4);

  Solution s;
  vector<vector<int> > v = s.threeSum(t);

  cout<<v.size();
}

 


联系
我们