LeetCodeOJブラシ問題の15-16【3 Sum(三数と問題)】
9590 ワード
本文は2つの問題である:【3数と(3 Sum)】と【最近の3数と(3 Sum Closest)】問題
第一部分は3 Sum問題を分析し、第二部分は3 Sum Closest問題を分析し、二つの問題の構想が似ているので、ここで一緒に分析する.その中の3 Sum問題はまだコンピュータ科学分野で解決されていない問題の一つのようだが,もちろん,より良い解決策はまだ見つかっていない.
1. 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.
意味は簡単です.つまり、整数配列を与えて、中から3つの数 Array Two Pointers
Solutions 1 3Sum -- 61~69ms は、まず配列を昇順に並べ替え、次に1つずつ整数を選択し、残りの配列要素から2つの数字を選択して、この3つの数字の和を0にします. 残りの2つの数字を選択すると、2番目の数字は1番目の数字の次の数字から始まります.これは、1番目の数字とそれ以前の数字が検索されたからです.解があれば、きっと見つけたに違いない.2番目の数字は1番目の数字の次の数字から後ろに選択されます.3番目の数字は最後の数字から前に選択されます.配列がソートされているので、存在すれば必ず見つかります. この考えのコードは以下の通りである: テストセットテストを行った后(ブログ园ここの画像はロードできないようです~):https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/15%203Sum/images/pic1.png ウィキペディアでは3 Sumについての説明がありますが、同時にStackOverflowを探してみると、現在はこの複雑度$O(N^2)$のソリューションしかなく、もっと良い解決策がない~~~ということに気づき、見つけられなかったのかもしれません.ウィキペディアで述べたアルゴリズムの思想は上の方法であり、偽コードを与えた: また、ウィキペディアで与えられた未解決のコンピュータ科学問題のアルゴリズムによれば、3 SUM問題を二次時間で解決できるかという問題があります.
https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/15%203Sum/images/pic2.png
ふろく GitHub-LeetCodesOJ GitHub-Blog
2. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
意味は簡単です.つまり、整数配列を与えて、中から3つの数 Array Two Pointers
Solutions 1 3Sum Closest -- 18ms この問題の思想は[3 Sum]を求める思想と類似しているので,同思想を用いて解くことができる. は、まず配列を昇順に並べ替え、次に1つずつ整数を選択し、残りの配列要素から2つの数字を選択し、この3つの数字の和sumを求める. 残りの2つの数字を選択すると、2番目の数字は1番目の数字の次の数字から始まります.これは、1番目の数字とそれ以前の数字が検索されたからです.解があれば、きっと見つけたに違いない.2番目の数字は1番目の数字の次の数字から後ろに選択されます.3番目の数字は最後の数字から前に選択されます.配列がソートされているので、存在すれば必ず見つかります. sumとtargetのサイズを比較し、等しい場合は、3数とtargetに最も近い距離が0であることを示します.この場合は限界であり、これより近いものはあり得ないので、直接このsumに戻ることができます. サイクルが終了するとresに記録されるのはtargetに最も近い3数和である. この考えのコードは以下の通りである: 試験セット試験後:https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/16%203Sum%20Closest/images/pic1.png 2 3Sum Closest -- 15ms 共有エリアで、 という解法を見つけました.私たちのさっきの考えは、まず1つの数字を確定して位置決めし、それから残りの2つの数字を遍歴することです.ここの考えはちょうど逆です.まず2つの数字を確定してから、残りの1つを探します. 配列を先にソートし、最初と最後の2つの数を位置決めします.次に、新しいターゲット数 二分法の時間的複雑さは$O(logn)$ である.検出された数字に基づいて、3数とcurSumを求め、最終的に要求されたtargetとの距離が最小距離mindiffより小さいかどうかを比較し、小さい場合は、最小距離mindiffに再付与するより小さな解を見つけることを示す.次の検索に進みます. 以上の解析から,このアルゴリズムの時間的複雑さは$O(Nlogn)$であることが分かった.方法1の$O(N^2)$よりも優れている. 次は私が改善したコードです: 試験セット試験後:https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/16%203Sum%20Closest/images/pic2.png
ふろく GitHub-LeetCodesOJ GitHub-Blog
第一部分は3 Sum問題を分析し、第二部分は3 Sum Closest問題を分析し、二つの問題の構想が似ているので、ここで一緒に分析する.その中の3 Sum問題はまだコンピュータ科学分野で解決されていない問題の一つのようだが,もちろん,より良い解決策はまだ見つかっていない.
1. 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)
意味は簡単です.つまり、整数配列を与えて、中から3つの数
a ,b ,c
を探して、a+b+c=0
にします.条件を満たすすべての三元グループ解セットを見つけます.また,解セットに重複する解は現れない.Solutions
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > res;
if(num.size()<3) return res;//
sort(num.begin(),num.end()); //
int beg , end , sum;
vector<int> tmp(3,0);
for(int i = 0;i<num.size()-2;++i){
// ,
if(num[i]>0)break;
if((i>0) && num[i]==num[i-1]) continue;
beg = i + 1;
end = num.size()-1;
while(beg < end){
sum=num[beg] + num[end] + num[i];
if( sum< 0) ++beg;
else if(sum > 0) --end;
else{
tmp[0] = num[i];
tmp[1] = num[beg];
tmp[2] = num[end];
res.push_back(tmp);
// ,
while(beg<end && num[beg]==tmp[1]) ++beg;
while(beg<end && num[end]==tmp[2]) --end;
if(beg>=end) break;
}
}
}
return res;
}
};
sort(S);
for i=0 to n-3 do
a = S[i];
start = i+1;
end = n-1;
while (start < end) do
b = S[start];
c = S[end];
if (a+b+c == 0) then
output a, b, c;
// Continue search for all triplet combinations summing to zero.
start = start + 1
end = end - 1
else if (a+b+c > 0) then
end = end - 1;
else
start = start + 1;
end
end
end
https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/15%203Sum/images/pic2.png
ふろく
2. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
意味は簡単です.つまり、整数配列を与えて、中から3つの数
a ,b ,c
を探して、a+b+c=0
にします.条件を満たすすべての三元グループ解セットを見つけます.また,解セットに重複する解は現れない.Solutions
sum != target
であれば現在の2つの数の間の距離dt=abs(sum-target)
と現在求められている最短距離dis
のどちらがより小さいかを判断し、dt<dis
であればtargetに近い解が現れたことを示す.この解の和resを記録します.class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
int n=num.size();
if(n<3)return 0;
sort(num.begin(),num.end());
int beg,end,sum=0;
int dis=INT_MAX;
int res;
for(int i=0;i<n-2;++i){
beg=i+1;
end=n-1;
while(beg<end){
sum=num[i]+num[beg]+num[end];
if(sum==target)return sum;
else if(sum<target) ++beg;
else --end;
int dt=(abs(sum-target));
if(dis>dt){
dis=dt;
res=sum;
}
}
}
return res;
}
};
newTarget = target - (num[start]+num[end])
を求め、残りの数値を2点で検索します.使用する二分検索で返される数値は、比較的条件に合致する配列の数値の下付き記号です.class Solution {
//
int findTarget(vector<int> &num, int start, int end, int target) {
if (start==end) return start;
if (end-start==1)
return abs(num[end]-target) > abs(num[start]-target)
? start : end;
int mid = (start+end)/2;
if (num[mid]==target) return mid;
else if(num[mid]>target)
return findTarget(num, start, mid, target);
else return findTarget(num, mid, end, target);
}
public:
int threeSumClosest(vector<int> &num, int target) {
int res=0;
if(num.size()<=3){
for(auto v : num) res+=v;
return res;
}
sort(num.begin(), num.end());
int start = 0;
int end = int(num.size()-1);
int mindiff = INT_MAX;
while (start<end-1) {
int newTarget = target - (num[start] + num[end]);
int p = findTarget(num, start+1, end-1, newTarget);
int curSum = num[start] + num[end] + num[p];
if (curSum == target) {
return target;
}else if(curSum > target) end--;
else start++;
mindiff = abs(mindiff)>abs(target-curSum) ? target-curSum : mindiff;
}
res=target-mindiff;
return res;
}
};
ふろく