C++ 中子数组的最大和等于 k
c++server side programmingprogramming
假设我们有一个名为 nums 的数组，目标值为 k，我们需要找到一个子数组，使得和等于 k 的最大长度。如果不存在，则返回 0。
因此，如果输入为 nums = [1, -1, 5, -2, 3]，k = 3，则输出为 4，因为子数组 [1, - 1, 5, -2] 的总和为 3，并且是最长的。
为了解决这个问题，我们将遵循以下步骤 −
ret := 0
定义一个映射 m
n := nums 的大小
temp := 0, m[0] := -1
初始化 i := 0，当 i < n，更新(将 i 加 1)，执行 −
temp := temp + nums[i]
如果 (temp - k) 在 m 中，则 −
ret := ret 和 i - m[temp - k] 中的最大值
如果 temp 不在 m 中，则 −
m[temp] := i
return ret
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSubArrayLen(vector<int<& nums, int k) {
int ret = 0;
unordered_map <int, int> m;
int n = nums.size();
int temp = 0;
m[0] = -1;
for(int i = 0; i < n; i++){
temp += nums[i];
if(m.count(temp - k)){
ret = max(ret, i - m[temp - k]);
}
if(!m.count(temp)){
m[temp] = i;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int< v = {1,-1,5,-2,3};
cout << (ob.maxSubArrayLen(v, 3));
}
输入
[1,-1,5,-2,3], 3
输出
4
