523. Continuous Subarray Sum

https://leetcode.com/problems/continuous-subarray-sum/description/

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Thoughts

是否存在和是K的倍数且长度大于1的子数组。subarray sum => presum，DP或窗口。当presum出现相同余数时，说明中间子数组的和为K的倍数，因为a[i]+a[i+1]+...+a[j]=n1K+q; a[i]+a[i+1]+...+a[j]+...+a[n]=n2K+q => a[j+1]+...+a[n]=(n2−n1)K。因此用presum记录sum%K的最早出现的位置。并且添加默认(0, -1)进presum来处理结果刚好是前缀的情况。

/*
 * @lc app=leetcode id=523 lang=cpp
 *
 * [523] Continuous Subarray Sum
 */

// @lc code=start
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> presum;
        presum[0] = -1;
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            const auto num = nums[i];
            sum += num;
            if (k != 0) sum %= k;
            if (presum.count(sum)) {
                if (i - presum[sum] > 1) return true;
            } else presum[sum] = i;
        }
        return false;
    }
};
// @lc code=end