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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个名为nums的数组和一个目标值k，我们必须找到一个总和为k的子数组的最大长度。如果不存在，则返回0。

因此，如果输入像nums = [1，-1，5，-2，3]，k = 3，则输出将是4，因为子数组[1，-1，5，-2]的总和为3，并且是最长的。

为了解决这个问题，我们将遵循以下步骤-

  • ret：= 0

  • 定义一张映射

  • n：= nums的大小

  • 温度：= 0，m [0]：= -1

  • 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

    • m [temp]：= i

    • ret：= ret和i-m [temp-k]的最大值

    • temp：= temp + nums [i]

    • 如果(temp-k)以m为单位，则-

    • 如果temp不在m中，则-

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

    以上是 C ++中最大大小的子数组总和等于k 的全部内容， 来源链接： utcz.com/z/343272.html

    回到顶部