总结在LeetCode中遇到的和为定值的一系列题目
在数组中碰到数组和为定值的大致可以分为这两类，一类是这些数不连续，从两个数和为定值到多个数和为定值，最后升级到动态规划的多重部分和问题；另一类是数必须是连续的子数组问题
两个数和为定值
这类题应该是最常见的题型了，常见的有两种方法：
- Hash，对每个a[i]，通过hash表快速判断出target-a[i]是否在数列中，这种方法不管数组是有序的还是无序的时间复杂度都是O(n)
- 双指针，用两个指针i，j分别指向数组的两端，依次判断
a[i] + a[j]与target的大小情况，大于target则j–，小于target则i++，如果数组是有序时间复杂度为O(n)，如果数组不是有序的时间复杂度为O(nlogn)
LeetCode 1
题意
给定有序的一个数组，求其中两个数的和刚好为定值target，返回这两个数的索引值
代码：1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
if (m.count(target - nums[i])) {
return {i, m[target - nums[i]]};
}
m[nums[i]] = i;
}
return {};
}
};
多个数和为定值
对于求解数组中m个数的和为定值的问题，枚举最开始的一个数都可以转换为m-1个数和为定值的问题，其最优的时间复杂度为O(n^m)。因为m如果大于2，排序的开销就不算在里面了，所以采用双指针的方法更加简单
LeetCode 3
题意：
求数组中3个数的和为定值的这个3个数的索引值
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int len = nums.size();
for(int i=0;i<len;i++)
{
if(i==0 || nums[i]!=nums[i-1]) // 去重
{
for(int j=i+1,k=len-1;j<k;)
{
if(nums[i]+nums[j]+nums[k] == 0)
{
vector<int> tmp = {nums[i],nums[j],nums[k]};
res.push_back(tmp);
j++;
while(j<k && nums[j]==nums[j-1]) j++;
k=len-1;
}
else if(nums[j]+nums[k]+nums[i]>0)
{
k--;
}
else
j++;
}
}
}
return res;
}
};
多重部分和问题
进阶可以转换成一个DP的题：有 n 种大小不同的数字 a[i]，每种 m[i] 个，判断是否可以从这些数字中选出若干个使他们的和恰好为 K。
设 dp[i+1][j] 为前 i 种数加和为 j 时第 i 种数最多能剩余多少个。（不能得到为-1）
这样状态转移方程为：
模板代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14int a[maxn],m[maxn],dp[maxm]; //a表示数，m表示数的个数，dp范围是所有数的和的范围
bool fun(int n,int K) //n表示数字种类,K表示组成的和
{
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for(int i=0; i<n; ++i) { //根据存储方式作出改变
for(int j=0; j<=K; ++j) {
if(dp[j] >= 0) dp[j] = m[i]; // 前i-1个数已经能凑成j了
else if(j < a[i] || dp[j-a[i]] <= 0) dp[j] = -1; // 否则，凑不成j或者a[i]已经用完，则无法满足
else dp[j] = dp[j-a[i]] - 1; // 否则可以凑成
}
}
return dp[K]>=0;
}
非负数组的子数组和为定值
这个题应该是比较基础的一道题：因为数组和一定递增的，所以采用滑动窗口的思想，维护滑动窗口的两个指针i和j，如果当前窗口和小于target时j++，如果当前窗口和大于target时i++
子数组和为定值
还是遍历一遍数组，使得总体的时间复杂度为O(n)，同时记录从第一个数到当前位置数的和为一张hash表，这个表对应的映射项可以是最早出现这个sum的index（以此来求最长子数组的长度），也可以是对应这个sum出现的次数（对应求满足条件的子数组个数）
LeetCode 560
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int len = nums.size();
unordered_map<int, int> m;
int sum = 0, res = 0;
m[0] = 1;
for(int i = 0; i < len; i++)
{
sum += nums[i];
// 加上剩余的值出现的次数
res += m[sum - k];
m[sum] ++;
}
return res;
}
};
变式
在上面那道题的基础上改为求满足条件的最长子数组的长度
1 | class Solution { |
子数组和小于等于定值
这里用到了两个辅助数组：min_value、min_index：min_value[i]表示以i位置开始往后加的最小累加和；min_index表示min_value对应的最小累加和的右边界，举个例子：
1 | arr 5 4 -3 -1 |
这两个辅助数组是能够在O(n)时间复杂内计算出来的：倒序遍历，min_value[i] 只需要判断min_value[i+1]的值是不是负数，如果是负数就加上，不是就到本身这里结尾。得到这样一个数组以后我们就可能轻易得到从某一个位置开始和最小的子数组。
有了这两个辅助数组以后，就可以采用滑动窗口的思想，左右两个指针都不回退，右指针以上面辅助数组进行累加，左指针正常遍历，使得总体的时间复杂度为O(n)
1 | class Solution { |
