Leetcode-3Sum

http://oj.leetcode.com/problems/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)

思路

  • 将数组排序,
  • a遍历数组a[0]....a[n-1];
  • a=a[i]时后面的问题就是:a[i+1]a[n-1]b+c =-a,记 b=a[j]=a[i-1],c=a[k]=a[n-1]. >若 b+c<-a,j++; >b+c>-a,j--;
    >b+c=-a 记录下来,并j++;
  • 还有一个问题就是unique triplet,所以a=a[i]要判断是否和a[i-1]相等,若相等子问题已经解答。也要判断b和c是否和之前的相同,若相同,就已经判断过了。

AC代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>  
#include <map>

using namespace std;

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
     sort(num.begin(), num.end());  
        vector<vector<int> > ans;  
        vector<int> temp;  
        for (int i = 0; i < num.size(); i++) {  
            if (i > 0 && num[i] == num[i - 1]) {  
                continue;  
            }  
            for (int j = i + 1; j < num.size(); j++) {  
                if (num[j] == num[j - 1] && j - 1 > i) {  
                    continue;  
                }  

                int k = - num[i] - num[j];  
                int left = j + 1, right = num.size() - 1, mid = 0;  
                while (left <= right) {  
                    mid = (left + right) >> 1;  
                    if (num[mid] > k) {  
                        right = mid - 1;  
                    }   
                    else if (num[mid] == k) {  
                        temp.push_back(num[i]);  
                        temp.push_back(num[j]);  
                        temp.push_back(num[mid]);  
                        ans.push_back(temp);  
                        temp.clear();  
                        break;  
                    }  
                    else {  
                        left = mid + 1;  
                    }  
                }  
            }  
        }  
        return ans;  
    }

    void print(vector< vector<int> > &result)
    {
        cout<<result.size()<<endl;
        for(int i = 0; i < result.size();i++)
        {
            for(int j = 0; j < result[i].size(); j++)
            {
                cout<<result[i][j]<<" ";
            }
            cout<<endl;
        }
    }
};

int main()
{
        Solution * mysolution = new Solution();
        vector<int> numbers;
        int time,c;
        cin>>time;
        while(time--)
        {
            cin>>c;
            numbers.push_back(c);
        }
        //vector<int> ans;
        vector<vector<int> > result;
        result = mysolution->threeSum(numbers);
        for(int i = 0; i < result.size();i++)
            {
                for(int j = 0; j < result[i].size(); j++)
                {
                    cout<<result[i][j]<<" ";
                }
                cout<<endl;
            }
        return 0;
}