Tổng mảng con bằng K trong C ++

Giả sử chúng ta có một mảng các số nguyên và một số nguyên k, chúng ta cần tìm tổng số các mảng con liên tục có tổng bằng k. Vì vậy, nếu mảng nums là [1, 1, 1] và k là 2, thì đầu ra sẽ là 2.

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

• xác định một bản đồ được gọi là tổng, tạm thời:=0, tổng [0]:=1 và ans:=0
• cho tôi trong phạm vi từ 0 đến kích thước của mảng
  • temp:=temp + n [i]
  • nếu tổng có k - tạm thời, thì
    • ans:=ans + tổng [k - temp]
  • tăng giá trị của tổng [-temp] lên 1
• trả lại ans

Ví dụ (C ++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int subarraySum(vector<int>& n, int k) {
      unordered_map <int, int> sums;
      int temp = 0;
      sums[0] = 1;
      int ans =0;
      for(int i =0;i<n.size();i++){
         temp+= n[i];
         if(sums.find(k-temp)!=sums.end()){
            ans += sums[k-temp];
         }
         sums[-temp]++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1};
   cout << (ob.subarraySum(v, 2));
}

Đầu vào

[1,1,1]
2

Đầu ra

2