Subarray Sums Divisible by K ใน C++: นับ Subarray ผลรวมหาร K ลงตัว

โจทย์

อาร์เรย์ A หาจำนวน subarray ต่อเนื่องไม่ว่าง ที่ผลรวมหาร k ลงตัว

ตัวอย่าง: A=[4,5,0,-2,-3,1], k=5 → 7 subarrays

แนวคิด: Prefix Sum + Modulo Counting

ถ้า prefix[j] % k == prefix[i] % k (i < j) → subarray (i+1..j) หาร k ลงตัว
นับความถี่ของแต่ละ modulo value

ขั้นตอน

1. map m; m[0] = 1 (prefix sum 0 นับ 1)
2. sum = 0, ans = 0
3. ลูป i = 0 ถึง n-1:
   • sum += A[i]
   • mod = (sum % k + k) % k (จัดการ negative)
   • ans += m[mod] (จำนวน prefix ก่อนหน้าที่มี mod เดียวกัน)
   • m[mod]++
4. คืน ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int subarraysDivByK(vector<int>& a, int k) {
        unordered_map<int, int> m;
        m[0] = 1;
        int sum = 0, ans = 0, n = a.size();
        for (int i = 0; i < n; i++) {
            sum += a[i];
            int mod = (sum % k + k) % k; // handle negative
            ans += m[mod];
            m[mod]++;
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {4,5,0,-2,-3,1};
    cout << ob.subarraysDivByK(v, 5); // 7
    return 0;
}

อินพุต / เอาต์พุต

Input: [4,5,0,-2,-3,1] 5

Output: 7

ความซับซ้อน

• Time: O(n)
• Space: O(k) - สูงสุด k ค่า mod ที่แตกต่าง