[C+][Leetcode]Two Sumおよびその変形
8361 ワード
目次
1.Leetcode 1両数の和
2.Leetcode 15三数の和
3.Leetcode 16最も近い三数の和
4.Leetcode 18四数の和
5.Leetcode 454四数の和II
1.Leetcode 1両数の和タイトル説明 構想分析 mapを使用してhashmapを作成し、追加の空間(n)を使用して、1回の遍歴で判断します.mapにいなければ参加し、mapでカウントします. 下書きに戻る必要があるのでsort+ダブルポインタでは不便です.
コード設計
2.Leetcode 15三数の和タイトル説明 構想分析 第1の考え方は,時間的複雑度がN*2,空間的複雑度がNである.3つの数については,2つの部分に分けて1つの数を固定し,Two Sumの考え方を用いて,この数の負数にTwo sumの解があるかどうかを判断する.Two Sumの解法は,一つのmapを用いてO(n)の遍歴を行い,遍歴しながらmapに入れることである.しかし配列に重複要素があることを考慮する必要があり,結果集合にも重複があるので,結果集合にこの解が既に存在していれば,これを加えないと判断する必要がある. の第2の考え方は,時間的複雑度がNlognである.高速ソートのライブラリ関数を用いて,ソート後の配列を得た.私たちも最初の考え方のように、1つの数を固定して、2つの数を探してからその数の負数です.ソート配列であるため、ターゲット数の右側にあり、互いに出会わないなど、2つのポインタを1つの範囲に設定する必要があります.コンストレイントを追加しないと、a[i]+a[j]=targetなどの繰り返しの組合せが表示されます.a[j]+a[i]=target.このほかにも、重複を避ける2つの戦略があります. 固定された数に対して、この数は繰り返し選択することはできません.繰り返しているとスキップします. は、2つのポインタの遍歴の過程について、解に遭遇した後、他の解を探すときに、前の解の繰返し値をスキップする必要がある.
コード設計
3.Leetcode 16最も近い三数の和タイトル説明 構想分析 三数の和の変形問題、ソート+二重ポインタ.コード設計
4.Leetcode 18四数の和タイトル説明 構想分析 3つの数の和を組み合わせる方法では、まず最初の2つの数を列挙し、次に2つのポインタを使用して後の2つの数を検索します.時間的複雑度はO(n^2 logn)である.列挙の過程で注意しなければならない.考慮すべきは、各数を考慮する際に繰り返さないことであり、4つの数の間に重複する数がある、例えば[0,0,0,0]target=0を入力と、結果集合は[[0,0,0]]となる.コード設計
5.Leetcode 454四数の和IIタイトル説明 構想分析 mapを使用してhash操作を行い、2つのグループに分けてそれぞれ遍歴し、1番目のグループの数とmapに格納します(数、この組み合わせが現れる回数).次にmapの検索機能を使用して2番目のグループの数とmapにあるかどうかを判断し、回数を統計します.この問題は組み合わせ数を返し、比較的簡単です.そして、繰り返しの組み合わせを考慮せず、組み合わせの下付きが異なる限り可能です.コード設計
1.Leetcode 1両数の和
2.Leetcode 15三数の和
3.Leetcode 16最も近い三数の和
4.Leetcode 18四数の和
5.Leetcode 454四数の和II
1.Leetcode 1両数の和
nums target， ， 。
。 ， 。
:
nums = [2, 7, 11, 15], target = 9
nums[0] + nums[1] = 2 + 7 = 9
[0, 1]
： （LeetCode）
：https://leetcode-cn.com/problems/two-sum
。 ， 。class Solution {
public:
vector twoSum(vector& nums, int target) {
vectorres;
int n=nums.size();
maphashmap;
for(int i=0;i 2.Leetcode 15三数の和
n nums， nums a，b，c ， a + b + c = 0 ？ 。
： 。
：
nums = [-1, 0, 1, 2, -1, -4]，
：
[
[-1, 0, 1],
[-1, -1, 2]
]
： （LeetCode）
：https://leetcode-cn.com/problems/3sum
。 ， 。
//
class Solution {
public:
void twoSum(vector&nums,int target,int k,vector>&res)
{
mapm;
for(int i=0;ipos;
pos.push_back(nums[i]);
pos.push_back(nums[m[target-nums[i]]]);
pos.push_back(nums[k]);
sort(pos.begin(),pos.end());
//
vector > ::iterator it=find(res.begin(),res.end(),pos);
if(it==res.end())//
res.push_back(pos);
}
else
m[nums[i]]=i;
}
}
vector> threeSum(vector& nums) {
vector< vector >res;
int n=nums.size();
for(int i=0;i //pass
class Solution {
public:
vector> threeSum(vector& nums) {
vector< vector >res;
// NlogN
sort(nums.begin(),nums.end());
int n=nums.size();
for(int i=0;i0&&nums[i]==nums[i-1])//
continue;
int target=-nums[i];
//
int low=i+1;
int high=n-1;
while(lowtarget)
high--;
else
{
vectorpos;
pos.push_back(nums[i]);
pos.push_back(nums[low]);
pos.push_back(nums[high]);
res.push_back(pos);
//
++low;
while(low 3.Leetcode 16最も近い三数の和
n nums target。 nums ， target 。 。 。
， nums = [-1，2，1，-4], target = 1.
target 2. (-1 + 2 + 1 = 2).
： （LeetCode）
：https://leetcode-cn.com/problems/3sum-closest
。 ， 。class Solution {
public:
int threeSumClosest(vector& nums, int target) {
int n=nums.size();
sort(nums.begin(),nums.end());
int cur=0;
int res=nums[0]+nums[1]+nums[2];
for(int i=0;itarget)
--high;
else
return target;
}
}
return res;
}
}; 4.Leetcode 18四数の和
n nums target， nums a，b，c d ， a + b + c + d target ？ 。
：
。
：
nums = [1, 0, -1, 0, -2, 2]， target = 0。
：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
： （LeetCode）
：https://leetcode-cn.com/problems/4sum
。 ， 。class Solution {
public:
vector> fourSum(vector& nums, int target) {
//
sort(nums.begin(),nums.end());
int n=nums.size();
vector>res;
for(int i=0;i0&&nums[i]==nums[i-1])
continue;
for(int j=i+1;ji+1&&nums[j]==nums[j-1])//
continue;
int ans=nums[i]+nums[j];
int low=j+1;
int high=n-1;
while(lowtarget)
--high;
else
{
vectorpos;
pos.push_back(nums[i]);
pos.push_back(nums[j]);
pos.push_back(nums[low]);
pos.push_back(nums[high]);
res.push_back(pos);
++low;
while(low 5.Leetcode 454四数の和II
A , B , C , D , (i, j, k, l) ， A[i] + B[j] + C[k] + D[l] = 0。
， A, B, C, D N， 0 ≤ N ≤ 500 。 -228 228 - 1 ， 231 - 1 。
:
:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
:
2
:
:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
： （LeetCode）
：https://leetcode-cn.com/problems/4sum-ii
。 ， 。class Solution {
public:
int fourSumCount(vector& A, vector& B, vector& C, vector& D) {
mapMap;
int res=0;
for(int i=0;i0&&A[i]==A[i-1])
// continue;
for(int j=0;j0&&B[j-1]==B[j])
// continue;
int ans=-(A[i]+B[j]);
if(Map.find(ans)==Map.end())
Map[ans]=1;
else
Map[ans]+=1;
}
}
for(int i=0;i0&&C[i-1]==C[i])
// continue;
for(int j=0;j0&&D[j-1]==D[j])
// continue;
int ans=C[i]+D[j];
if(Map.find(ans)!=Map.end())
res+=Map[ans];
}
}
return res;
}
};