523. 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.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

1. The length of the array won't exceed 10,000.

2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

暴力解time complexity為O(n^2)，用了兩個for loop去把所有可能形成的subarray算一遍。

// Brute Force
bool checkSubarraySum(vector<int>& nums, int k) { // time: O(n^2); space: O(1)
    if (nums.empty()) return false;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        int sum = nums[i];
        for (int j = i + 1; j < n; ++j) {
            sum += nums[j];
            if (sum == k || k != 0 && sum % k == 0) return true;
        }
    }
    return false;
}

Hashmap可以幫忙記錄前一次sum%k對應到的position在哪，只要確認之前出現的index和當前index差距大於1就可以滿足條件。

// Hashmap
bool checkSubarraySum(vector<int>& nums, int k) { // time: O(n); space: O(k)
    if (nums.empty()) return false;
    unordered_map<int, int> m; // <remainder, position index>
    m[0] = -1; // initialize
    int sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
        sum = (k == 0) ? sum : sum % k;
        if (m.count(sum)) {
            if (i - m[sum] > 1) return true;
        } else m[sum] = i;
    }
    return false;
}

也可以在節省一點只用hashset去存出現過的sum % k值，但要多一個變數紀錄上一輪的sum % k值，等到下一輪再insert到hashset。這樣就可以確保subarray長度大於1 。

// Hashset
bool checkSubarraySum(vector<int>& nums, int k) { // time: O(n); space: (k)
    if (nums.empty()) return false;
    unordered_set<int> st; // stores result after modulus
    int sum = 0, pre = 0; // insert pre to hashset in the next iteration to ensure the size of subarray >= 2
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
        sum = (k == 0) ? sum : sum % k;
        if (st.count(sum)) return true;
        st.insert(pre);
        pre = sum;
    }
    return false;
}