[interval and topic prefix and] prefix and + hash table application questions

Title Description

This is a LeetCode Upper 「560. And for K Subarray 」, The difficulty is 「 secondary 」.

Tag : 「 The prefix and 」、「 Hashtable 」

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

Example 1：

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

 Output ：2

Copy

Example 2：

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

 Output ：2

Copy

Tips ：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

The prefix and + Hashtable

This is a classic prefix and application problem .

Statistics with each

nums[i]

For the end , And for

k

The number of subarrays of is the answer .

We can preprocess prefixes and arrays sum（ Prefixes and array subscripts default from

1

Start ）, For solving with a certain

nums[i]

For the end of , And for

k

Number of subarrays for , In essence, it is to solve in

[0, i]

in ,sum How many values in the array are

sum[i + 1] - k

Number of numbers , This can be used during traversal 「 Hashtable 」 Synchronous recording .

Code ：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length, ans = 0;
        int[] sum = new int[n + 10];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 1; i <= n; i++) {
            int t = sum[i], d = t - k;
            ans += map.getOrDefault(d, 0);
            map.put(t, map.getOrDefault(t, 0) + 1);
        }
        return ans;
    }
}

Copy

• Time complexity ： The complexity of preprocessing prefix and is

O(n)

, The complexity of the statistical answer is

O(n)

. The overall complexity is

O(n)

• Spatial complexity ：

O(n)

Last

This is us. 「 Brush through LeetCode」 The first of the series No.560 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .