Tổng mảng con liên tục chia hết cho K (Continuous Subarray Sum) trong C++

Cho mảng số không âm và số nguyên k. Kiểm tra có mảng con liên tiếp độ dài ≥ 2 với tổng chia hết cho k hay không.

Ví dụ: [23,2,4,6,7], k=6 → true ([2,4] tổng 6).

Thuật toán (Prefix Sum Mod + Hash Map)

1. Tính prefix sum modulo k (nếu k!=0).
2. Lưu chỉ số đầu tiên của mỗi modulo.
3. Nếu modulo gặp lại và khoảng cách ≥ 2 → true.

Mã nguồn C++

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

class Solution {
public:
    bool checkSubarraySum(vector& nums, int k) {
        unordered_map mp{{0,-1}};
        int sum=0;
        for (int i=0; i= 2) return true;
            if (!mp.count(sum)) mp[sum]=i;
        }
        return false;
    }
};

int main() {
    vector v = {23,2,4,6,7};
    Solution ob;
    cout << ob.checkSubarraySum(v, 6); // 1 (true)
    return 0;
}

Đầu vào / Đầu ra

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

Output: 1