Fast simple O(n) C++ solution with unordered_map and n+1 size loop


  • 0
    D

    This implementation avoids special cases for the 0 index or the final index by having a loop from 0 to nums.size() inclusive, and just not adding to the sum in the final iteration. I also use find() and insert() to avoid doing more hash table lookups than necessary, which makes it quite fast (32 ms).

    class Solution {
    public:
        int maxSubArrayLen(vector<int>& nums, int k) {
            // Compute prefix sums (prefix_sums[i] = sum from 0 to i-1 of nums[i])
            // Find pairs in this sequence whose difference is exactly k
            // Use hash table to remember indexes of earlier prefix sums in sequence
            unordered_map<int, int> prefix_sum_map;
            int sum = 0, result = 0;
            for (int i=0; i < nums.size() + 1; i++) {
                auto pair = prefix_sum_map.find(sum - k);
                if (pair != prefix_sum_map.end()) {
                    result = max(result, i - pair->second);
                }
                // insert() will not add if it's already in the map, because we want the leftmost index
                prefix_sum_map.insert(make_pair(sum, i));
                if (i < nums.size()) {
                    sum += nums[i];
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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