Clearance sword refers to Offer——The sword refers to Offer II 010. and the sub-array of k

1.题目描述

剑指 Offer II 010. 和为 k 的子数组

给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数.

示例 1：

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例 2：

输入:nums = [1,2,3], k = 3
输出: 2

2.解题思路与代码

2.1 解题思路

This problem requires summing up contiguous subarrays of a number,Then the problem of summing continuous subarrays like this can first be solved by using prefix sum.We denote prefixes and arrays as sum[] The original array is recorded as num[],Prefixes and arrays have the following two properties

• 前缀和数组第 i The bit value is the original array [0, i] The sum of all elements in bits
• sum[i]-sum[j] (i>j) equal to the original array [i+1, j] 上元素之和

基于这两个特性,We can know the contiguous subarray sum required by the title k,In fact, it is to find whether there are two positions on the prefix and the array i 和 j （其中 j>i）使得 sum[j]-sum[i]=k,After this is deduced, the problem is very simple.

We have the above formula sum[j]-sum[i]=k 进行变形得到 sum[j]-k=sum[i],When we get the prefix and the array, we traverse the original array from the beginning to the end num[],And the meaning of this deformed formula is when we find the first j The prefix and hour of the location,在 j Whether there is a prefix and equals to the first j Prefix and subtract of positions k,每存在一个 sum[i] 等于 sum[j]-k Add the statistics 1.由于需要在 j Look up the prefix sum before,To reduce traversal we use a hash table to store the number of prefixes and counts previously computed.这里有一点需要注意,The prefix sum array requires one more bit than the original array,And the prefix sums the first of the array 0 位置为 0.

以题目示例 nums = [1,1,1], k = 2 为例进行图解.
First we initialize the prefix sum array and hash table,The prefix and array bits are one more than the original array to store the initial 0,Indicates that the prefix sum is yes when no number is selected at this time 0,并将 0 放入哈希表中

Start calculating the prefix sum,Traverse the first position of the original array,此时 sum[1] 等于 1,Then according to the previous formula,We need to find the first 1 Whether there is a prefix and equals in front of the bitsum[1]-k 即 -1,It was not found in the hash table,于是将 sum[1] Continue to traverse after putting into the hash table

Continue to calculate the prefix sum,此时 sum[2] 等于 2,Then need to see sum[2] Whether there is a prefix and equals before sum[2]-2 即 0,can be obtained from the hash table 0 出现了一次,统计结果加一,并将 sum[2] 放入哈希表中

Finally traverse to the first of the original array 2 位,此时 sum[3] 等于 3,Then you need to find whether it exists in the previous prefix sum sum[3]-2 即 1,在哈希表中存在 1,and only appeared once,So the result is incremented by one,最终得到结果是 2.

2.2 代码

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        if (nums.length == 1) {
    
            return nums[0] == k ? 1 : 0;
        }
        // 初始化前缀和数组,The length is one bit more than the original array,并且第 0 位设置为 0
        int[] sum = new int[nums.length + 1];
        sum[0] = 0;
        // Initialize the hash table storage
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int ans = 0;
        for (int i = 1; i < nums.length + 1; i++) {
    
            // 计算前缀和,and calculate what needs to be looked up target
            sum[i] = sum[i - 1] + nums[i - 1];
            int target = sum[i] - k;
            // Read from hash table target included in the results
            ans += map.getOrDefault(target, 0);
            // Store the prefix sum of the current bit into the hash table
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        return ans;
    }
}

2.3 测试结果

通过测试

3.总结

• Solve using prefix sum and hash table
• Prefixes and arrays need to be initialized to use 0 占位