AlgoPressAppearance
0325-和等于k的最长子数组长度
https://leetcode.cn/problems/maximum-size-subarray-sum-equals-k
给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长连续子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。
示例 1:
输入: nums = [1,-1,5,-2,3], k = 3
输出: 4
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
示例 2:
输入: nums = [-2,-1,2,1], k = 1
输出: 2
解释: 子数组 [-1, 2] 和等于 1，且长度最长。
提示：
1 <= nums.length <= 2 * 10^5
-10^4 <= nums[i] <= 10^4
-10^9 <= k <= 10^9
思路
动态规划，定义 dp, dp[i,j] 表示从 i 到 j 的连续数组和，如果和等于k，记录 max = Math.Max(max,j-i)
注意：直接使用二维动态规划，会内存溢出，说明数组空间过大，需要优化为1维
参考代码
动态规划，空间过大
csharp
public class Solution {
public int MaxSubArrayLen(int[] nums, int k) {
int n = nums.Length;
int[,] dp = new int[n,n];
//初始化
int max = 0;
for(int i=0; i<n; i++){
dp[i,i] = nums[i];
if(dp[i,i] == k){
max = 1;
}
}
//状态转移
for(int i=0; i<n-1; i++){
for(int j = i+1; j<n; j++){
dp[i,j] = dp[i,j-1] + nums[j];
if(dp[i,j] == k){
max = Math.Max(max,j-i+1);
}
}
}
return max;
}
}
去掉二维数组，只记录当前值，会时间超时
csharp
public class Solution {
public int MaxSubArrayLen(int[] nums, int k) {
int n = nums.Length;
int max=0;
for(int i=0; i<n; i++){
int sum = 0;
for(int j = i; j<n; j++){
sum+=nums[j];
if(sum == k){
max = Math.Max(max,j-i+1);
}
}
}
return max;
}
}
思路2 【哈希表，前缀和】
当超时时，可以考虑哈希表加速， 使用 Hash 表记录前缀和
csharp
public class Solution {
public int MaxSubArrayLen(int[] nums, int k) {
int n = nums.Length;
Dictionary<int,int> dict = new Dictionary<int,int>();
int sum = 0;
int max = 0;
for(int i=0; i<nums.Length; i++){
sum += nums[i];
if(sum == k){
max = Math.Max(max,i+1);
}
if(!dict.ContainsKey(sum)){
dict.Add(sum,i);
}
int presum = sum - k;
if(dict.ContainsKey(presum)){
max = Math.Max(max,i - dict[presum]);
}
}
return max;
}
}
复习：20220604
csharp
public class Solution {
public int MaxSubArrayLen(int[] nums, int k) {
int preSum = 0;
Dictionary<int,int> dict = new Dictionary<int,int>();
int len = 0;
dict.Add(0,0); //记录0位置的前缀和，这样当 preSum == k 的时候，也可以直接计算
for(int i=0; i<nums.Length; i++){
preSum += nums[i];
int target = preSum - k;
if(dict.ContainsKey(target)){
len = Math.Max(len, i - dict[target] + 1);
}
if(!dict.ContainsKey(preSum)){
dict.Add(preSum,i+1);
}
}
return len;
}
}