Link to the problem

The problem is here: https://leetcode-cn.com/problems/continuous-subarray-sum/

Problem description

Given an array nums of non-negative numbers and a number k, return true if there exists a subarray of nums (with at least 2 elements) that sums up to a multiple of k.

Idea

It is a very typical problem to use the prefix-sum algorithm. We define , and for simplicity, . The problem is actually to find a tuple s.t. .

Here we need to use a math trick: .

Instead of memorizing the prefix-summations, we need to store the reminders. And for each , check whether there exists a , s.t. .

Implementation

My implementation is this:

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = -1;
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        int rem = sum % k;
        auto it = mp.find(rem);
        if (it == mp.end()) {
            mp[rem] = i;
        } else if (it->second <= i - 2) {
            return true;
        }
    }
    return false;
}