Simple 9 lines C++


  • 0
    class Solution {
    public:
        int subarraySum(vector<int>& nums, int k) {
            int count = 0;
            unordered_map<int, int>m;
            int sum = 0;
            for(auto x: nums){
                m[sum]++;
                sum += x;
                if(m.count(sum - k) > 0) count += m[sum - k];
            }
            return count;
        }
    };
    

  • 0
    S

    Can you explain logic behind it ? (thanks in advance)


  • 0

    @sk_3003 Say nums = [1,2,3,4,5], k = 5.

    • First we put 0 into hash map, so that when sum equals k, it will be counted, means m.count(sum - k) = m.count(0).
    • Put the sum of nums[0] to nums[i] into hash map. When nums = [1,2,3,4,5], we will put sum = 1,3,6,10,15 into hash map. Since k = 5, at position 3, sum = 6, we count(6 - 5) = count(1), and 1 occurs at position 0, we know the numbers between position 0 and 3 must sums to 5, result++. Same happens when sum = 15, we count(15 - 5) = 10, and it occurs before at previous position, we know it must be a 5 in that position, result++, and finally we return 2.

    Hope it helps.


Log in to reply
 

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