Leetcode 560 prefix and + hash table

Leetcode 560 The prefix and + Hashtable

Title Description

Give you an array of integers nums And an integer k , Please count and return The array is k The number of consecutive subarrays of .

Example 1：

Input ：nums = [1,1,1], k = 2
Output ：2

Thought analysis

Pre knowledge

Prefix and not much introduction

Algorithm ideas

1. Add to the current subscript i Prefix of element and prefixSum, namely sum（num[0:i]）
2. It is required to end with the current element and k The number of , The o i The prefix and before the element are prefixSum - k The number of
3. Therefore, the hash table needs to store the prefix and at the end of the element before the current element is x The number of
4. Update hash table , Sum the prefix with prefixSum Number of updates , If it didn't exist before value Set to 1, On this basis, existence adds 1. There may have been prefixes and before prefixSum, Because the value of the element may be negative

difficulty ： What does the hash table store ？

Add the subscript of the currently traversed element i
The hash table stores ：
sum（num[0:1]） The number of
sum（num[0:i2） The number of
sum（num[0:3]） The number of
…
sum（num[0:i-1]） The number of

Code

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int prefixSum = 0;
        int count = 0; // Result set 
        for(int i = 0; i < nums.length; i++){
    
            prefixSum += nums[i];

            // Find the sum ending with the current element as k Result , Add to result set 
            count += map.getOrDefault(prefixSum - k, 0);

            // to update map
            map.put(prefixSum, map.getOrDefault(prefixSum,0)+1);
        }

        return count;
   
    }
}