目录
1. 两数之和
167. 两数之和 II - 输入有序数组
653. 两数之和 IV - 输入 BST
560. 和为 K 的子数组
523. 连续的子数组和
713. 乘积小于 K 的子数组
152. 乘积最大子数组
15. 三数之和
16. 最接近的三数之和
18. 四数之和
454. 四数相加 II
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
class Solution {
public:
vector twoSum(vector& nums, int target) {
std::unordered_map map;
for(int i = 0; i < nums.size(); i++) {
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
map.insert(pair(nums[i], i));
}
return {};
}
};
167. 两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
class Solution {
public:
vector twoSum(vector& numbers, int target) {
vector res;
int l=0,r=numbers.size()-1;
while(true){
int sum=numbers[l]+numbers[r];
if(sum==target) {
res.push_back(l+1);
res.push_back(r+1);
break;
}
else if(sum>target){
r--;
}
else l++;
}
return res;
}
};
653. 两数之和 IV - 输入 BST
给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
class Solution {
public:
unordered_set set;
bool findTarget(TreeNode* root, int k) {
if(root==nullptr) return false;
if(set.count(k-root->val)) return true;
else set.insert(root->val);
return findTarget(root->left,k)||findTarget(root->right,k);
}
};
560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
前缀和
class Solution {
public:
int subarraySum(vector& nums, int k) {
unordered_map mp;
mp[0] = 1;
int count = 0, pre = 0;
for(int i=0;i
523. 连续的子数组和
（没有完全掌握）
给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
子数组大小 至少为 2 ，且
子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。
如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。
【同余定理】 【哈希表】【简化前缀和】
同余定理：如果两个整数m、n满足n-m能被k整除，那么n和m对k同余
即 ( pre(j) - pre (i) ) % k == 0 则 pre(j) % k == pre(i) % k
推导 => pre (i) % k = (a0 + a1 + ... + ai) % k = (a0 % k + a1 % k + ... ai % k ) % k （该推导在简化前缀和的时候有用，说明当前前缀和 % k 不会影响后面的前缀和 % k ）
哈希表 存储 Key ：pre(i) % k
Value： i
遍历过程：
-
计算前缀和 pre( j ) % k
-
当pre(j) % k 在哈希表中已存在，则说明此时存在 i 满足 pre(j) % k == pre(i) % k ( i < j )
HashMap里，已知Key，可以取到Value 即i的值， 最后 判断 j - i >= 2 是否成立 即可
3.当 pre(j) % k 不存在于哈希表，则将 (pre(j) % k, j ) 存入哈希表
class Solution {
public:
unordered_map map;
bool checkSubarraySum(vector& nums, int k) {
if(nums.size()<2) return false;
for(int i=1;i=2) return true;
}
else map[temp]=i;
}
return false;
}
};
713. 乘积小于 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
class Solution {
public:
int numSubarrayProductLessThanK(vector& nums, int k) {
int n = nums.size(), ret = 0;
int prod = 1;
int left=0;
for(int right=0;right=k){
prod/=nums[left++];//前缀乘积之和大于等于k 左指针右移 并且去掉左指针当前的元素
}
ret+=right-left+1;//滑动窗口内子数组的数量
}
return ret;
}
};
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
class Solution {
public:
int maxProduct(vector& nums) {
int maxF = nums[0], minF = nums[0], ans = nums[0];
for (int i = 1; i < nums.size(); ++i) {
//储存之前的最大值和最小值
int mx=maxF;
int mn=minF;
maxF=max(maxF*nums[i],max(nums[i],mn*nums[i]));//类似动态规划了
minF=min(minF*nums[i],min(nums[i],mx*nums[i]));
ans = max(maxF, ans);
}
return ans;
}
};
15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public:
vector> threeSum(vector& nums) {
sort(nums.begin(),nums.end());
vector> result;
for(int i=0;i 0 && nums[i] == nums[i-1]) continue;//去重 不然会出现重复的解
int left=i+1;
int right=nums.size()-1;
while(left-nums[i]) right--;
else if(nums[left]+nums[right]<-nums[i]) left++;
else{
result.push_back({nums[i],nums[left],nums[right]});
left++;
right--;
//找到解之后 相同的left和right不能再使用 需要去重 while循环
while(left
16. 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
class Solution {
public:
int threeSumClosest(vector& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int best = 1e8;
for(int i=0;i0&&nums[i]==nums[i-1]) continue;
while(left
18. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
class Solution {
public:
vector> fourSum(vector& nums, int target) {
vector> result;
sort(nums.begin(),nums.end());
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 left=j+1;
int right=nums.size()-1;
while(lefttarget-temp){
right--;
}
else if((long)nums[right]+nums[left]
454. 四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
class Solution {
public:
int fourSumCount(vector& A, vector& B, vector& C, vector& D) {
unordered_map umap; //key:a+b的数值，value:a+b数值出现的次数
// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
for (int a : A) {
for (int b : B) {
umap[a + b]++;
}
}
int count = 0; // 统计a+b+c+d = 0 出现的次数
// 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
for (int c : C) {
for (int d : D) {
if (umap.find(0 - (c + d)) != umap.end()) {
count += umap[0 - (c + d)];
}
}
}
return count;
}
};
