Continuous Subarray Sum ตรวจสอบสับอาร์เรย์ติดกันที่หารด้วย k ลงตัวใน C++

ให้อาร์เรย์จำนวนไม่ติดลบ และ k หาว่ามี subarray ติดกันขนาด ≥ 2 ที่ผลรวมหารด้วย k ลงตัว (เป็น n×k) หรือไม่

ตัวอย่าง: [23,2,4,6,7], k=6 → true (subarray [2,4] ผลรวม 6)

วิธีแก้ปัญหา (Prefix Sum Modulo + Hash Map)

1. map m เก็บ {prefix_sum_mod_k: index}, m[0] = -1
2. sum = 0
3. วน i = 0 ถึง n-1:
   • sum += nums[i]
   • ถ้า k ≠ 0: sum %= k
   • ถ้า sum อยู่ใน m และ i - m[sum] ≥ 2 → true
   • ถ้า sum ไม่อยู่ใน m: m[sum] = i
4. คืน false

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

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

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

Input

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

Output

1