523. Continuous Subarray Sum

源链接:https://leetcode.com/problems/continuous-subarray-sum/

题目描述: 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.

解题思路:    核心思想是累加取模,如果sum(nums[0]-nums[i]) % k == sum(noms[0]-nums[j]) (假设 j > i),那么sum(nums[I] – num[j]) 必然是k的倍数,这里的”-“指的是从noms[I] 到nums[j]    如此, 问题便简化成一个查找问题,只需找到从0到当前元素的和对k取模后结果是否在先前的结果中出现过,如果出现过,则必有 i-i sum up to the muliple of k,这里需要注意下,至少两个元素!

代码:

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int pre = 0, sum = 0; // 这里pre就是为了保证至少两个元素而存在的
        unordered_set<int> modk;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            int mod = k == 0 ? sum : sum % k;
            if (modk.count(mod)) return true;
            modk.insert(pre);
            pre = mod;
        }
        return false;
    }
};

发表评论