C++ 4 lines O(n)


  • 1
    V
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> sums({{0, 1}});
        for (auto i = 0, sum = 0, res = 0; i < nums.size(); sum += nums[i++], ++sums[sum]) {
            res += sums[sum + nums[i] - k];
            if (i == nums.size() - 1) return res;
        }
    }
    

    Also a three-liner:

    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> sums({{0, 1}});
        for (auto i = 0, sum = 0; i < nums.size(); sum += nums[i++], sums[INT_MAX] += sums[sum - k], ++sums[sum]);
        return sums[INT_MAX];
    }
    

  • 0
    Y

    @votrubac brilliant solution. Thank you for sharing


Log in to reply
 

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