> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/presum/continuous-subarray-sum.md).

# 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来处理结果刚好是前缀的情况。

```cpp
/*
 * @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


```