首页 🍒LeetCode,🐶算法

题目

fHh4D5p7n2.png

思路

按照朴素思想遍历数组中每个长度大于2的子数组然后判断是否符合条件,这样会超时,需要优化。

可以用一个前缀数组pre把nums数组的每个前缀和求出来然后直接用,pre[i] - pre[j]就是i~j子数组的和。
if ((pre\[i] - pre\[j]) % k == 0 && i - j >= 2)则返回true。

如果(pre[i] - pre[j]) % k == 0 则pre[i]和pre[j] % k的结果是一样的,那么可以求每个前缀和取余k的值,如果一样并且差大于等于2则返回true。

可以用一个map存每个前缀和取余k的值。

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        if (n < 2) return false;
        map<int, int> mp;
        mp[0] = -1;
        int pre[n];
        pre[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] + nums[i];
        }
        for (int i = 0; i < n; i++) {
            int m = pre[i] % k, p;
            if (mp.count(m)) {
                p = mp[m];
                if (i - p >= 2) return true;
            }
            else {
                mp[m] = i;
            }
        }
        return false;
    }
};



文章评论