523. Continuous Subarray Sum

同余 O(n) time O(n) space
a % k = c
(a + sum) % k = c
sum % k = 0
需要sum的数字个数大于1
和974. Subarray Sums Divisible by K不同，k有可能为0，所以必须给前缀和维护一个hashmap

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> m; // 利用一个map保存<前缀和余数, 下标>
        m[0] = -1; // 因为连续的子数组是从头开始的，则需要提前先保存一个余数0
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (k != 0) sum %= k; // k如果是0，跳过即可
            if (m.count(sum)) { // 如果map里没有当前余数，保存即可，否则检查是否相隔至少2个数
                 if (i - m[sum] > 1) return true; // 这个if不能跟上一层的merge！！！因为有可能有相邻的
            } else {
                m[sum] = i;
            }
        }
        return false;
    }
};

前缀和O(n²) time O(n) space

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> presum(n + 1);
        for (int i = 1; i <= n; ++i) {
            presum[i] = presum[i - 1] + nums[i - 1];
        }
        for (int len = 1; len <= n - 1; ++len) {
            for (int i = 0; i < n - len; ++i) {
                int j = i + len;
                int sum = presum[j + 1] - presum[i];
                if (k == 0) {
                    if (sum == 0) return true;
                    continue;
                }
                if (sum / k * k == sum) return true;
            }
        }
        return false;
    }
};