523. Continuous Subarray Sum

Description:

https://leetcode.com/problems/continuous-subarray-sum/#/description

Boundary:

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.

Algorithm:

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.

Code: 

class Solution {
public:
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;
modk.insert(pre);
pre = mod;
}
return false;
}
};

Tips:

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