Prefix and (continuously updated)

The problem-solving idea of prefix and ：
The problem-solving thinking of prefix and is relatively fixed , That is, when we loop the array to the subscript N when , Before you need to use an array N-1 The result of the calculation of the term （ It doesn't have to be with , It may also be a product ）, At this point, we should consider whether we should simplify the solution by calculating the cumulative value during the array loop , In this way, we have the problem-solving idea of prefix and .

Understand the idea , It's time to consider , How should we save the accumulated results ？

The title clearly requires that no additional space is allowed , Directly modify the array in place
When space complexity is not limited , It is better to open up additional space for computing , Avoid data pollution
When calculating, if you only need to obtain the cumulative results of the previous time , You can store the value of each element at the end of the array in the form of array
If each calculation needs to obtain the results of the previous several or more times for comparison , The recommended method of hash table , This can reduce the time complexity

Example 1： Given an array of integers and an integer k , Please find the array with k The number of consecutive subarrays of .(Offer 010)

The explanation of the great God ：
This topic is very concise , Is to find what is an integer in the array k The number of consecutive subarrays .
If the value of this question is not negative , That's the standard sliding window problem , But because of negative numbers , Sliding window thinking is useless .
Through analysis , This question should belong to the last of the four situations we listed above . The idea is as follows ：

Initialize an empty hash table and pre_sum=0 Prefixes and variables
Set return value ret = 0, Used to record the number of subarrays that meet the meaning of the question
In the process of looping the array , By modifying the array in place , Calculate the cumulative sum of the array
Add and subtract the current integer K Result , Check the hash table for the existence of
If the key value , Prove that taking a certain point of the array as the starting point to the current position satisfies the meaning of the question ,ret Add equals to add this key Value corresponding value
Judge whether the current cumulative sum is in the hash table , If exist value+1, If it does not exist value=1
Eventually return ret that will do
But here we should pay attention to the prefix and boundary problems just mentioned .
In this scenario, we calculate , You need to consider if you use an array nums[0] A continuous subarray that begins with a is enough to satisfy the meaning of the question ？
At this time, our hash table is still empty , There is no way to calculate the prefix and ！ So when you encounter such problems , You need to insert a... In the hash table by default {0:1} The key/value pair ,
It is used to solve the special scenario that successive subarrays starting from the array meet the meaning of the problem .
Let's start solving the problem ！

//  The method of using prefix and ：
class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
    //  Create a HashMap Relate the prefix to its number of occurrences 
    Map<Integer,Integer> map=new HashMap<Integer,Integer>();
    //  Create a variable to record before n Xiang He 
    int sum=0;
    //  Create a variable to record the number of subarrays that meet the conditions 
    int count=0;
    //  Why should we start with （0,1） Make connections ？ Avoid using arrays nums[0] A continuous subarray starting with k
    map.put(0,1);

    for(int num:nums){
    
        sum=sum+num;
        //  Judge whether the sum between the current position and a previous position can meet the conditions 
        //  If there is count Add the number of sum-k Corresponding key value 
        count=count+map.getOrDefault(sum-k,0);
        map.put(sum,map.getOrDefault(sum,0)+1);
    }
    return count;
    }
}