前缀和+数学公式

​ 首先从暴力开始考虑，暴力枚举所有区间，并加上前缀和的优化来判断，这样时间复杂度是$O(N^2)$的，我们要考虑继续优化。

利用等式变形。

因为图中要保证区间>=2，枚举需要注意区间问题。

如图：右边的等式有了后，从左到右枚举，边枚举边存储，这样就能保证枚举s[j]的时候，左边的数%k都已经枚举过了，存储可以用哈希表来存储。

1. 预处理前缀和
2. 从左到右枚举，边枚举边存储，查询对于s[j]来说，哈希表是否存在s[j] % k

时间复杂度$O(N)$，空间复杂度$O(N)$

AC代码

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n + 1);
        unordered_set<int> set;
        //预处理前缀和
        for (int i = 0 ; i < n ; i ++) s[i + 1] = s[i] + nums[i];
        //枚举终点
        for (int i = 2 ; i <= n ; i ++) {
            set.insert(s[i - 2] % k);
            if (set.count(s[i] % k))
                return true;
        }
        return false;
    }
};