Tổng mảng con liên tục trong C ++

Giả sử chúng ta có một danh sách các số không âm và một số nguyên đích k, chúng ta phải viết một hàm để kiểm tra xem mảng có một mảng con liên tục có kích thước ít nhất là 2 mà tổng lên đến bội số của k, tổng đến n * k trong đó n cũng là một số nguyên. Vì vậy, nếu đầu vào là [23,2,4,6,7] và k =6, thì kết quả sẽ là True, vì [2,4] là một mảng con liên tục có kích thước 2 và tổng lên đến 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một ánh xạ m, đặt m [0]:=-1 và sum:=0, n:=kích thước của mảng nums
• cho tôi trong phạm vi từ 0 đến n - 1
  • sum:=sum + nums [i]
  • nếu k khác 0, thì sum:=sum mod k
  • nếu m có tổng và i - m [sum]> =2, thì trả về true
  • nếu m không có tổng, hãy đặt m [sum]:=i
• trả về false

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

1