AlgoPressAppearance
0560-和为K的子数组
https://leetcode.cn/problems/subarray-sum-equals-k
给你一个整数数组 nums 和一个整数k ，请你统计并返回该数组中和为k的连续子数组的个数。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7
思路 : 动态规划 【会超出内存】
可以重复使用数组的数字 动态规划： dp[i,j] 表示从 i 加到 j 的所有数值的和 dp[i,j] = dp[i,j-1]+nums[i]; 二维dp会爆出内存
参考代码
csharp
public class Solution {
public int SubarraySum(int[] nums, int k) {
int[,] dp = new int[nums.Length,nums.Length];
//初始化，只能从i开始
int max = 0;
for(int i=0; i<nums.Length; i++){
dp[i,i] = nums[i];
if(dp[i,i] == k){
max++;
}
}
//状态转移
for(int i=0; i<nums.Length; i++){
for(int j=i+1;j<nums.Length;j++){
dp[i,j] = dp[i,j-1]+nums[j];
if(dp[i,j] == k){
max++;
}
}
}
return max;
}
}
思路2：优化内存
因为每一行开始计算，我们都要重新计算sum，而且每次都只用到前面的 preSum 所以不需要保存所有的状态 从i开始，重置设置 curSum = 0, 然后依次累加和，发现等于 k 的时候， max++ 注意：
- 单独一个数字也是连续和，所以 nums[i] = k 也算1个
- 因为题目要求是连续的就可以，所以不用暂停，持续往后面计算 如 k = 2, 则 1,1,-1,1 就会有两个序列满足 1,1 和 1,1,-1,1
参考代码
csharp
public class Solution {
public int SubarraySum(int[] nums, int k) {
//初始化，只能从i开始
int max = 0;
int curSum = 0;
//状态转移
for(int i=0; i<nums.Length; i++){
curSum = nums[i];
if(curSum == k){
max++;
}
for(int j=i+1;j<nums.Length;j++){
curSum+=nums[j];
if(curSum == k){
max++;
}
}
}
return max;
}
}
复习：两层循环 20220519
不需要单独计算一个数的 sum ， 直接 j = i 开始累积，为 k 则 count+1
csharp
public class Solution {
public int SubarraySum(int[] nums, int k) {
int sum;
int count=0;
for(int i=0; i<nums.Length; i++){
sum = 0;
for(int j=i;j<nums.Length; j++){
sum+=nums[j];
if(sum == k){
count++;
}
}
}
return count;
}
}
复习：前缀和 20220519
注意前缀和 preSum[0] 表示前0个数字的和，所以数组要增加1
csharp
public class Solution {
public int SubarraySum(int[] nums, int k) {
int n = nums.Length;
int[] preSum = new int[n+1];
preSum[0] = 0;
for(int i=0; i<n; i++){ //计算前缀和
preSum[i+1] = preSum[i]+nums[i];
}
//计算
int count = 0;
for(int i=0; i<n; i++){
for(int j=i; j<n; j++){
//群建和 [i..j] 注意下标偏移
if( preSum[j+1] - preSum[i] == k){
count++;
}
}
}
return count;
}
}
复习：前缀和+哈希表
csharp
public class Solution {
public int SubarraySum(int[] nums, int k) {
int n = nums.Length;
Dictionary<int,int> dict = new Dictionary<int,int>();
dict.Add(0,1); // 对于下标为 0 的元素，前缀和为 0，个数为 1
int preSum = 0;
int count = 0;
for(int i=0; i<n; i++){
preSum += nums[i];
if(dict.ContainsKey(preSum - k)){
count += dict[preSum - k];
}
if(dict.ContainsKey(preSum)){
dict[preSum] += 1;
}
else{
dict.Add(preSum,1);
}
}
return count;
}
}