245      阿裏雲  技術社區[雲棲]

[LeetCode]15.3Sum

【題目】

    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
*   題目: 15.3Sum
*   網址：https://oj.leetcode.com/problems/3sum/
*   結果：AC
*   來源：LeetCode
*   總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        int i,j,target,start,end;
        int Len = num.size();
        vector<int> triplet;
        vector<vector<int>> 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<vector<int>> result;
    Solution solution;
    vector<int> 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;
}

【測試】

最後更新：2017-04-03 12:54:36

  上一篇： Unity中資源動態加載的幾種方式比較

  下一篇： 實用bash命令記錄