4LeetCodeの合計
4sum Leetcode
【トピック】
4Sum
受け入れられた合計：3493 総提出数：16137 私の提出物与えられた配列Sのn整数、要素はありますかに、b、c、およびdにSそのようなに+b+c+d=ターゲット？ターゲットの合計を与える配列内のすべての一意の4つ組を検索します。
注意：
- 4つ組の要素（に、b、c、d）降順ではない必要があります。 （すなわち、に≤b≤c≤d）。
- 解集合には、重複する4つ組が含まれていてはなりません。
/********************************* * Date: 2014-01-18 * Author: SJF0115 * Title: 4Sum * Source: http://oj.leetcode.com/problems/4sum/ * Result: AC * Source: LeetCode * to sum up: **********************************/ #include #include #include #include #include using namespace std class Solution { public: vector fourSum(vector &num, int target) { int i,j,start,end int Len = num.size() vector triplet vector triplets set sets //sort sort(num.begin(),num.end()) for(i = 0i the current value needs to be increased else if(target > curSum){ start ++ } // Less than -> The current value needs to be reduced. else{ end -- } }//while } }//for / / Use set to de-weight set::iterator it = sets.begin() for( it != sets.end() it++) triplets.push_back(*it) return triplets } } int main() { vector result Solution solution vector 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 = 0i
[題名]
n個の整数の配列が与えられた場合、配列Sにa + b + c + d =ターゲットとなる要素a、b、c、dがありますか？配列内の一意の4要素グループを見つけて、それらの合計がターゲットになるようにします。
注意：
4つの要素でグループ（あいうえお）に、する必要がある満足させる減少しないソート。 （これはに≤b≤c≤d）。
ソリューションセットに重複を含めることはできません要素グループ。
【分析】
- 配列を並べ替える
- クォータニオンの最初の2つを決定します（a、b）
- 残りの配列をトラバースして2つの外側の2つ（c、d）を決定する、cdを決定するというアイデア 3Sum 最後の2つのデータと同じように、左右の近似の二分探索を決定します。
- 重複排除時にセットセットを使用する
[コード]
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)
【テスト】
入力： [-1,0,1,2、-1、-4]、-1 期待： [[-4,0,1,2]、[-1、-1,0,1]]
入力： [-3、-2、-1,0,0,1,2,3]、0 期待： [[-3、-2,2,3]、[-3、-1,1,3]、[-3,0,0,3]、[-3,0,1,2]、[-2 、-1,0,3]、[-2、-1,1,2]、[-2,0,0,2]、[-1,0,0,1]]