523. Continuous Subarray Sum




The boundary is really complex.

  1. k = 0.If k == 0,  the answer will be TRUE if there are more than 2 components sum to 0. Otherwise, it will be FALSE.
  2. k = 1 || k = -1
    1. The answer will be TURE if there are more than 2 components in the array.
    2. The answer will be FLASE if there is 0 or 1 components.
  3. Otherwise
    1. Go through the array to calculate sum[i] % k, and insert the residual in the array;
    2. If there are continuous components summing to n*k, then the new residual will be found in the array;
    3. Because we are looking for continuous subarray of size at least 2, the insertion of residual must be delayed. i.e. If there is a, b, c in the array, b%k ==0 and a,c %k !=0. The residual of a & a+b should be the same. But we need to make sure that when finding (a+b)%k in the array, a%k has not been inserted.


  1. Use for loop, in each cycle, calculate sum[i] by adding up nums[i]
  2. If k != 0, calculate mod = sums[i]%k; otherwise, mod = sum[i]
  3. Find if there is mod in the rsdl array, if found, return TRUE
  4. insert the residual of the PREVIOUS cycle into the rsdl array.


class Solution {
bool checkSubarraySum(vector<int>& nums, int k) {
int n = nums.size(), sum = 0, pre = 0;
unordered_set<int> modk;
for (int i = 0; i < n; ++i) {
sum += nums[i];
int mod = k == 0 ? sum : sum % k;
if (modk.count(mod)) return true;
pre = mod;
return false;


  1. Learn to use unordered_set and its count() function.
  2. Remember the beautiful technique of “delay of insertion”.

Leave a Reply

Your email address will not be published. Required fields are marked *