continuous-subarray-sum

523. Continuous Subarray Sum

• 如果子數列各個元素除以 k 的餘數和，可以被 k 整除的話，則連續子數列的總和必定可以被 k 整除。
• 初始化一個 Map modSeen 儲存 {餘數: index}。
• edge case: modSeen[0] = -1

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k)
    {
        int n = nums.size();
        int prefixMod = 0;
        unordered_map<int, int> modSeen;

        modSeen[0] = -1;

        for (int i = 0; i < n; ++i)
        {
            prefixMod = (prefixMod + nums[i]) % k;
            if (modSeen.count(prefixMod))
            {
                if (i - modSeen[prefixMod] > 1)
                {
                    return true;
                }
            }
            else
            {
                modSeen[prefixMod] = i;
            }
        }
        return false;
    }
};```


- T: $O(n)$
- S: $O(n)$