程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode之3Sum

LeetCode之3Sum

編輯：C++入門知識

【題目】

3Sum

Total Accepted: 6032 Total Submissions: 35898My Submissions

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)

Discuss

【題意】

給定n個整數的數組S，是否在數組S中有元素a，b，C，使得A + B + C =0？在數組中找出獨一無二的三元素組，使得他們之和為0。

注意：

在三元素組（A，B，C）中，必須滿足非遞減排序。（即A≤B≤C）

該解決方案集中一定不能包含重復的三元素組。

【分析】

先排序，然後二分查找，復雜度 O(n^2*log n)。a + b + c = 0 即 b + c = -a

題目思路與劍指Offer之和為S的連續正數序列博文思路一致。可以參考一下解題思路。

另有：點擊打開鏈接詳細總結

【代碼】

/*********************************
*   日期：2014-01-18
*   作者：SJF0115
*   題號: 3Sum
*   來源：http://oj.leetcode.com/problems/3sum/
*   結果：AC
*   來源：LeetCode
*   總結：
**********************************/
#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    vector > threeSum(vector &num) {
        int i,j,target,start,end;
        int Len = num.size();
        vector triplet;
        vector> triplets;
        //排序
        sort(num.begin(),num.end());
        for(i = 0;i < Len-2;i++){
            //跳過重復元素
            if(i != 0 && num[i] == num[i-1]){
                continue;
            }
            //a + b + c = 0
            target = -num[i];
            //二分查找
            start = i + 1;
            end = Len - 1;
            while(start < end){
                int curSum = num[start] + num[end];
                //相等 -> 目標
                if(target == curSum){
                    triplet.clear();
                    triplet.push_back(num[i]);
                    triplet.push_back(num[start]);
                    triplet.push_back(num[end]);
                    triplets.push_back(triplet);
                    //注意： 跳過重復元素
                    while(start < end && num[start] == num[start + 1]){
                        start ++;
                    }
                    while(start < end && num[end] == num[end - 1]){
                        end --;
                    }
                    start ++;
                    end --;
                }
                //大於 -> 當前值小需要增大
                else if(target > curSum){
                    //注意：跳過重復元素
                    while(start < end && num[start] == num[start + 1]){
                        start ++;
                    }
                    start ++;
                }
                //小於 -> 當前值大需要減小
                else{
                    //注意：跳過重復元素
                    while(start < end && num[end] == num[end - 1]){
                        end --;
                    }
                    end --;
                }
            }//while
        }//for
        return triplets;
    }
};
int main() {
    vector> result;
    Solution solution;
    vector vec;
    vec.push_back(-2);
    vec.push_back(0);
    vec.push_back(0);
    vec.push_back(2);
    vec.push_back(2);
    result = solution.threeSum(vec);
    for(int i = 0;i < result.size();i++){
        for(int j = 0;j < result[i].size();j++){
            printf("%d ",result[i][j]);
        }
        printf("\n");
    }
    return 0;
}