C++ easy understand solution with comment


  • 4
    M
    // O(n) complexity.
    // Core idea: for the same cumulative sum value, we
    // only keep it's first appearance, so at last the
    // subarray is guaranteed to be the longest.
    // Also, note the brilliant idea of using the sum value
    // as the key of the map.
    int maxSubArrayLen(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        m[0] = -1;
        int sum = 0;
        int maxLen = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (!m.count(sum)) m[sum] = i;
            if (m.count(sum - k)) maxLen = max(maxLen, i - m[sum - k]);
        }
        return maxLen;
    }

  • 0
    N

    @machuiwen said in C++ easy understand solution with comment:

    ray is guaranteed

    why we need m[0]=-1?


  • 0
    B

    @nguyenton68 The -1 at m[0]=-1 is just a virtual index. For example, in the array [-2, -1, 2, 1] and k=1. We know that -1+2==1. Therefore, whose index are 1 and 2. But on unordered_map m, their index are actually 0 and 2. The value on the left has a -1 in it. That's why we need to set m[0] to be -1 to suit for the case where we started counting from the very beginning.


Log in to reply
 

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