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

[LeetCode]18.4Sum

【題目】

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

【題意】

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

注意：

在四元素組（a，b，c，d）中，必須滿足非遞減排序。 （即a≤b≤c≤d）

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

【分析】

1. 對數組排序
2. 確定四元數中的前兩個（a，b）
3. 遍曆剩餘數組確定兩外兩個（c，d），確定cd時思路跟3Sum確定後兩個數據一樣，二分查找左右逼近。
4. 在去重時采用set集合

【代碼】

/*********************************
*   日期：2014-01-18
*   作者：SJF0115
*   題號: 4Sum
*   來源：https://oj.leetcode.com/problems/4sum/
*   結果：AC
*   來源：LeetCode
*   總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        int i,j,start,end;
        int Len = num.size();
        vector<int> triplet;
        vector<vector<int>> triplets;
        set<vector<int>> sets;
        //排序
        sort(num.begin(),num.end());
        for(i = 0;i < Len-3;i++){
            for(j = i + 1;j < Len - 2;j++){
                //二分查找
                start = j + 1;
                end = Len - 1;
                while(start < end){
                    int curSum = num[i] + num[j] + num[start] + num[end];
                    //相等 -> 目標
                    if(target == curSum){
                        triplet.clear();
                        triplet.push_back(num[i]);
                        triplet.push_back(num[j]);
                        triplet.push_back(num[start]);
                        triplet.push_back(num[end]);
                        sets.insert(triplet);
                        start ++;
                        end --;
                    }
                    //大於 -> 當前值小需要增大
                    else if(target > curSum){
                        start ++;
                    }
                    //小於 -> 當前值大需要減小
                    else{
                        end --;
                    }
                }//while
            }
        }//for
        //利用set去重
        set<vector<int>>::iterator it = sets.begin();
        for(; it != sets.end(); it++)
            triplets.push_back(*it);
        return triplets;
    }
};
int main() {
    vector<vector<int>> result;
    Solution solution;
    vector<int> vec;
    vec.push_back(-3);
    vec.push_back(-2);
    vec.push_back(-1);
    vec.push_back(0);
    vec.push_back(0);
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    result = solution.fourSum(vec,0);
    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:38

  上一篇： 存儲那些事兒（一）：異構虛擬化一種實現SMIS

  下一篇： Java中的Cookie(1)——基本操作