C ++中的连续子数组总和

假设我们有一个非负数的列表和一个目标整数k,我们必须编写一个函数来检查数组是否具有大小至少为2的连续子数组,其总和为k的倍数,总和为n * k其中n也是整数。因此,如果输入类似于[23,2,4,6,7],并且k = 6,则结果将为True,因为[2,4]是大小为2的连续子数组,总和为6。

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

  • 制作一个映射m,设置m [0]:= -1和sum:= 0,n:= nums数组的大小

  • 对于i,范围为0至n – 1

    • sum:= sum + nums [i]

    • 如果k不为零,则sum:= sum mod k

    • 如果m有和,且i – m [sum]> = 2,则返回true

    • 如果m没有和,则设置m [sum]:= i

  • 返回假

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool checkSubarraySum(vector<int>& nums, int k) {
      unordered_map<int, int> m;
      m[0] = -1;
      int sum = 0;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         sum += nums[i];
         if(k)
         sum %= k;
         if(m.count(sum) && i - m[sum] >= 2){
            return true;
         }
         if(!m.count(sum)) m[sum] = i;
      }
      return false;
   }
};
main(){
   vector<int> v = {23,2,4,6,7};
   Solution ob;
   cout << (ob.checkSubarraySum(v, 6));
}

输入值

[23,2,4,6,7]
6

输出结果

1