Python C++使用prefix sum mod k + hash map解Leetcode523 Continuous Subarray...

Python C++使用prefix sum mod k + hash map解Leetcode523  Continuous Subarray Sum。模k，前綴和 (mod k) 總共有 k 個可能，為 0,1,...k-1。 對於這個條件 1 less eq nums.length less eq 10^5 O(n^2) 解可能會導致 TLE。 對於此條件 1 less leq k less eq 2^31 - 1，陣列版本解決方案可能會導致 MLE。 然而，注意使用前綴和 mod k 的hash映射是一個有效解法。

modulo k there are 0,1,...k-1 totally k possible for prefix sum (mod k).

For this constraint 1  less eq nums.length  less eq 10^5 an O(n^2) solution may lead to TLE.

For this constraint 1 less leq k less eq 2^31 - 1, an array version solution might lead to MLE. 

C++解請進

A hash map with care on prefix sum mod k to use is however a tip.

[codes on Leetcode]https://leetcode.com/problems/continuous-subarray-sum/solutions/5277106/mod-k-prefix-sum-hash-table-array-from-mle-to-86ms-beats-99-75/

[Leetcode Playlist]https://www.youtube.com/watch?v=B1GQlUN08lk&list=PLYRlU
BnWnd5IdDHk2BjqXwesydU17z_xk

class Solution {
public:
    inline static int hash_map(vector& nums, int k, int n){
        unordered_map mod_k;// 1 <= k <= 2^31 - 1
        int prefix=0;
        mod_k.reserve(n);
        mod_k[0]=-1;//sum can begin from index i=0
        for(int i=0; imod_k[prefix]+1) 
                    return 1;
            }
            else
                mod_k[prefix]=i;// mod_k[prefix]=i
        }
        return 0;
    }
    inline static int array(vector& nums, int k, int n){
        vector mod_k(k, INT_MIN);// mod k=0,1,...,k-1
        int prefix=0;
        mod_k[0]=-1;//sum can begin from index i=0
        for(int i=0; i<n; i++){
            prefix+=nums[i];
            prefix%=k;
            if (mod_k[prefix]!=INT_MIN){
                if (i>mod_k[prefix]+1)
                    return 1;
            }
            else mod_k[prefix]=i;// mod_k[prefix]=i
        }
        return 0;
    }
    static bool checkSubarraySum(vector& nums, int k) {
        int n=nums.size();
        if (n<2) return 0; //its length is at least two
        if (k>=n) return hash_map(nums, k, n);
        return array(nums, k, n);
    }     
};