1. leetcode-1 兩數(shù)之和
1.1 題目描述
給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target率翅，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù)灭将，并返回他們的數(shù)組下標(biāo)榆浓。
你可以假設(shè)每種輸入只會對應(yīng)一個答案影涉。但是莱褒，你不能重復(fù)利用這個數(shù)組中同樣的元素提佣。
1.2 解題思路
使用一個HashMap肚吏，來建立數(shù)字和其坐標(biāo)位置之間的映射方妖，掃描一遍，對其中的每一個整數(shù)nums[i]须喂，查找target-nums[i]在map中是否存在即可吁断。若存在，則輸出i與 target-nums[i]的下標(biāo)即可.
1.3 代碼
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int, int> hashmap;
for(int i=0;i<nums.size();i++){
if(hashmap.count(target-nums[i])>0){
res.push_back(hashmap[target-nums[i]]);
res.push_back(i);
break;
}else{
hashmap[nums[i]] = i;
}
}
return res;
}
};
2. leetcode-371 兩整數(shù)之和
2.1 題目描述
不使用運算符 + 和 - ???????坞生，計算兩整數(shù) ???????a 仔役、b ???????之和。
2.2 解題思路
不斷的異或和與是己，異或的結(jié)果是不含進(jìn)位的加又兵，與得到的是每一位的進(jìn)位，讓結(jié)果和進(jìn)位繼續(xù)異或（無進(jìn)位加）卒废，直到進(jìn)位為0
2.3 代碼
class Solution {
public:
int getSum(int a, int b) {
while(b){
// 防止 AddressSanitizer 對有符號左移的溢出保護(hù)處理
auto c = ((unsigned int)a&b) << 1;
//求兩數(shù)相加的進(jìn)位沛厨，與運算和左移運算捌肴，得相加之后進(jìn)位所在位得值
a = a^b; //異或操作：不進(jìn)位加法
b = c;
}
return a;
}
};
3. leetcode-167 兩數(shù)之和 II - 輸入有序數(shù)組
3.1 題目描述
給定一個已按照升序排列 的有序數(shù)組埃跷，找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)近她。
函數(shù)應(yīng)該返回這兩個下標(biāo)值 index1 和 index2劫哼，其中 index1 必須小于 index2。
說明:
返回的下標(biāo)值（index1 和 index2）不是從零開始的诸衔。
你可以假設(shè)每個輸入只對應(yīng)唯一的答案尼酿，而且你不可以重復(fù)使用相同的元素恭理。
示例:
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 。因此 index1 = 1, index2 = 2 剿牺。
3.2 解題思路
雙指針法企垦，使用兩個指針，初始分別位于第一個元素和最后一個元素位置晒来，比較這兩個元素之和與目標(biāo)值的大小钞诡。如果和等于目標(biāo)值，我們發(fā)現(xiàn)了這個唯一解湃崩。如果比目標(biāo)值小荧降，我們將較小元素指針增加一。如果比目標(biāo)值大攒读，我們將較大指針減小一誊抛。
3.3 代碼
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res;
int i=0, j=numbers.size()-1;
while(i<j){
int sum = numbers[i] + numbers[j];
if(sum==target){
res.push_back(i+1);
res.push_back(j+1);
break;
}else if(sum<target) i++;
else j--;
}
return res;
}
};
4. leetcode-15 三數(shù)之和
4.1 題目描述
給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a整陌，b，c 瞎领，使得 a + b + c = 0 泌辫？找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組九默。
例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]震放，
滿足要求的三元組集合為：
[[-1, 0, 1],
[-1, -1, 2]]
4.2 解題思路
采用三指針法
- 先把數(shù)組排序好
- 先固定一個值，然后采用雙指針驼修，三個值的和為0則保存殿遂，如果大于0則右指針左移，如果小于0則左指針右移乙各。
可以做個剪枝優(yōu)化墨礁，有以下幾種情況需要優(yōu)化。
- 遍歷到正數(shù)直接break耳峦，因為數(shù)字已經(jīng)是有序的了恩静，如果第一個要固定的數(shù)是正的話，那之后的數(shù)字也必然是正的蹲坷，無需考慮驶乾。
- 其次，如果在前幾個固定的數(shù)中已經(jīng)使用到后面為正數(shù)的數(shù)了循签，我們也不需要把這些正數(shù)作為固定的數(shù)级乐，因為這些數(shù)在之前的解使用過了。
- 從第二個數(shù)起县匠，如果和前面的數(shù)字相等风科，就跳過撒轮。我們不想把相同數(shù)字固定兩次。
4.3 代碼
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int n=nums.size();
if(n<3) return res;
sort(nums.begin(), nums.end());
for(int i=0;i<n-2;i++){
int left=i+1;
int right=n-1;
if(nums[i]>0) return res;
if(i>0 && nums[i-1]==nums[i]) continue;
while(left<right){
int sum = nums[i] + nums[left] + nums[right];
if(sum<0) left++;
else if(sum>0) right--;
else{
res.push_back({nums[i], nums[left++], nums[right--]});
while(left < right && nums[left-1]==nums[left]) left++;
while(left < right && nums[right+1]==nums[right]) right--;
}
}
}
return res;
}
};
5. leetcode-16 最近的三數(shù)之和
5.1 題目描述
給定一個包括 n 個整數(shù)的數(shù)組 nums 和 一個目標(biāo)值 target丐重。找出 nums 中的三個整數(shù)腔召，使得它們的和與 target 最接近。返回這三個數(shù)的和扮惦。假定每組輸入只存在唯一答案臀蛛。
例如，給定數(shù)組 nums = [-1崖蜜，2浊仆，1，-4], 和 target = 1.
與 target 最接近的三個數(shù)的和為 2. (-1 + 2 + 1 = 2).
5.2 解題思路
和上一題一樣啊豫领，采用三指針法
- 先把數(shù)組排序好抡柿，用res記錄距離target最近的和
- 先固定一個值，然后采用雙指針等恐，三個值的和與target更近則更新res洲劣，如果sum>target則右指針左移，否則左指針右移课蔬。
5.3 代碼
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n=nums.size();
if(n<3) return -1;
sort(nums.begin(), nums.end());
int res = nums[0] + nums[1] + nums[2];
for(int i=0;i<n-2;i++){
int left=i+1;
int right=n-1;
while(left<right){
int sum = nums[i] + nums[left] + nums[right];
if(abs(res-target)>abs(target-sum)) res = sum;
if(sum<target) left++;
else right--;
}
}
return res;
}
};
6. leetcode-923 三數(shù)之和的多種可能
6.1 題目描述
給定一個整數(shù)數(shù)組 A囱稽，以及一個整數(shù) target 作為目標(biāo)值，返回滿足 i < j < k 且 A[i] + A[j] + A[k] == target 的元組 i, j, k 的數(shù)量二跋。
由于結(jié)果會非常大战惊，請返回 結(jié)果除以 10^9 + 7 的余數(shù)。
示例 ：
輸入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
輸出：20
解釋：
按值枚舉（A[i]扎即，A[j]吞获，A[k]）：
(1, 2, 5) 出現(xiàn) 8 次；
(1, 3, 4) 出現(xiàn) 8 次谚鄙；
(2, 2, 4) 出現(xiàn) 2 次各拷；
(2, 3, 3) 出現(xiàn) 2 次。
提示：
3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300
6.2 解題思路
參考
由于題目限制 0 <= A[i] <= 100闷营， 可以比較容易的想到去遍歷0到100的數(shù)撤逢，而不是遍歷數(shù)組A
首先記錄0到100的數(shù)組出現(xiàn)的次數(shù)
我們需要找到3個數(shù)相加等于target。我們可以通過數(shù)字的順序i粮坞，j找到k蚊荣。找到i，j莫杈，k之后就是簡單乘法互例，如有數(shù)字相等，就用排列組合計算筝闹。
為什么可以用排列組合計算媳叨。我們可以考慮把A排序腥光，比如 1 1 1 1 2 2 5 5。那么我們可以找到 1 2 5 三個數(shù)字糊秆。單個數(shù)字每個索引其實都是合法的武福，那么就是 4 * 2 * 2。 如果target = 3痘番，那么應(yīng)該是 1 1 1捉片。這就是很顯然的3個坑，4個數(shù)按順序去填汞舱，c43伍纫。
6.3 代碼
class Solution {
public:
int threeSumMulti(vector<int>& A, int target) {
constexpr int kMaxN = 100;
constexpr int kMod = 1e9 + 7;
vector<long> c(kMaxN+1, 0);//數(shù)組分配空間
for(int num:A) ++c[num];//計數(shù)
long ans = 0;
for(int i = 0; i <= target; ++i){
for(int j = i; j <= target; ++j){
const int k = target - i - j;
if (k < 0 || k >= c.size() || k < j) continue;
if(!c[i] || !c[j] || !c[k]) continue;
if(i == j && j == k){
ans += c[i] * (c[i]-1)*(c[i]-2) / 6;
}
else if(i == j && j != k){
ans += c[i] * (c[i]-1) / 2 * c[k];
}
else if(i != j && j == k){
ans += c[j] * (c[j]-1) / 2 * c[i];
}
else{
ans += c[i] * c[j] * c[k];
}
}
}
return ans % kMod;
}
};
7. leetcode-18 四數(shù)之和
7.1 題目描述
給定一個包含 n 個整數(shù)的數(shù)組 nums 和一個目標(biāo)值 target，判斷 nums 中是否存在四個元素 a昂芜，b莹规，c 和 d ，使得 a + b + c + d 的值與 target 相等泌神？找出所有滿足條件且不重復(fù)的四元組良漱。
注意：
答案中不可以包含重復(fù)的四元組。
示例：
給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]欢际，和 target = 0债热。
滿足要求的四元組集合為：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
7.2 解題思路
和三數(shù)之和差不多的思路，先固定兩個數(shù)字幼苛，然后采用雙指針。
- 先把數(shù)組排序好
- 先固定一個值焕刮，然后采用雙指針舶沿，四個值的和為0則保存，如果大于0則右指針左移配并，如果小于0則左指針右移括荡。
- 注意：因為不能有重復(fù)的數(shù)字出現(xiàn)，因此固定第一個數(shù)字時溉旋，從第二個數(shù)起（i>0）畸冲，如果和前面的數(shù)字相等，就跳過观腊。我們不想把相同數(shù)字固定兩次邑闲；固定第二個數(shù)字時，需要滿足j-i>1梧油。
7.3 代碼
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n=nums.size();
vector<vector<int>> res;
if(n<4) return res;
sort(nums.begin(), nums.end());
for(int i=0;i<n-3;i++){
if(i>0 && nums[i-1]==nums[i]) continue;
for(int j=i+1;j<n-2;j++){
int left = j+1;
int right = n-1;
if(j-i>1 && nums[j-1]==nums[j]) continue;
while(left<right){
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if(sum<target) left++;
else if(sum>target) right--;
else{
res.push_back({nums[i], nums[j], nums[left++], nums[right--]});
while(left<right && nums[left-1]==nums[left]) left++;
while(left<right && nums[right+1]==nums[right]) right--;
}
}
}
}
return res;
}
};
8. leetcode-454 四數(shù)相加 II
8.1 題目描述
給定四個包含整數(shù)的數(shù)組列表 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 量淌。所有整數(shù)的范圍在 -228 到 228 - 1 之間，最終結(jié)果不會超過 231 - 1 嫌褪。
例如:
輸入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
輸出:
2
解釋:
兩個元組如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
8.2 解題思路
- 建立一個hashmap,記錄AB數(shù)組的組合和以及出現(xiàn)的次數(shù)
- 計算CD數(shù)組的組合和呀枢，在hashmap中查找相反數(shù)
8.3 代碼
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int ans = 0;
unordered_map<int,int> hashmap;
for(auto a : A){
for(auto b : B){
int sum = a + b;
hashmap[sum] ++;
}
}
for(auto c : C){
for(auto d : D){
int need = -(c + d);
if(hashmap.count(need)) ans = ans + hashmap[need];
}
}
return ans;
}
};
