C++ 中和 k 相等的子数组最大大小

假设我们有一个名为 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

• 返回 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

Arnab Chakraborty

更新于: 2020-11-18

730 次查看

开启您的 职业生涯

通过完成课程获得认证

开始