Share my 32 ms C++ solution(with unordered_map)


  • 0
    J
    class Solution {
    public:
        bool checkSubarraySum(vector<int>& nums, int k) {
            // if length < 2
            if (nums.size() < 2)    return false;
            //k == 0, make k = INT_MAX to check if there is a subarray sums to 0
            if (k == 0) {
                k = INT_MAX;
            }
            k = abs(k);
            //map sum to k buckets
            unordered_map<int, int> sum2count;
            //map the corresponded end index, start from 1
            unordered_map<int, int> sum2index;
            int sum = 0;
            //tricks, see empty array as sum 0, and its end index is 0 
            sum2count[0] = 1;
            sum2index[0] = 0;
            for (int i = 0; i < nums.size(); ++i) {
                sum += nums[i];
                sum2count[sum % k]++;
                if (sum2index.find(sum % k) == sum2index.end()) {
                    sum2index[sum % k] = i + 1;
                }
                if (sum2count[sum % k] > 1 && i - sum2index[sum % k] > 0) {
                    return true;
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.