Zero Basic Algorithm 100 Days Day 4 – Prefix Sum (Basic Algorithm)

⭐️Introduction⭐️ _ _

Hello everyone, I’m a stalker. The first three days are all about the more classic three [graph theory algorithms] , and you still need to have a certain algorithm foundation to understand. But today, we are going to talk about one of the basic algorithms – prefix sum. A very practical and easy algorithm. Today we will talk about the basic one-dimensional [prefix sum] to help Xiaobai understand it better.

⭐️Catalog⭐️ _ _

🔥1. Background story

🔆 2. What are prefixes and arrays?

😾3. How to preprocess to get prefix and array

🎃 4. Use of prefixes and arrays

🍋5. Prefix and template questions practice

1), area and retrieval

2), consecutive subarrays and

3), continuous array

🔥1. Background story

Bugs Bunny has a lot of radish pits at home, and each pit has a certain number of radishes. In order to test Bugs Bunny, Bugs Bunny’s mother asked him to give him two pits x and y each time, and let him tell himself how many radishes there are in total from pit x to pit y within a certain period of time? Bugs Bunny has to run to the pit x number of radishes every time, and then run to the x+1 pit…. Until y, when he got the answer happily and went home, his mother told it – you are overtime !

Why time out?

Bugs Bunny pondered this question, and every time he went to the radish pit to count a number, it was so stupid, why not take a notebook and write it down? Bugs Bunny patted his head angrily, but thought about it again, every time his mother gave x, y. I still have to use pit x+ pit x+1+ pit x+2 all the way to pit y. This is too slow! Proper O(n) time complexity.

Until Bugs Bunny’s friend Little Black Rabbit came, Bugs Bunny told him about his troubles, and Little Black said it wasn’t easy? So the two took the book and went to the radish pit. First use the array a to record the number of each radish pit, a[i] represents the number of radishes in the i-th pit. Then Xiao Hei gave Bugs Bunny an array S after a while, and told Xiao Hei to tell Bugs Bunny every time his mother told you x and y, using S[y]-S[x-1] is the answer.

After Bugs Bunny does the same, the answer can be given in the next second after the mother reads x and y, which is a proper O(1) time complexity. And this mysterious array S – is the prefix sum array!

🔆 2. What are prefixes and arrays?

In fact, through the background story, you can clearly feel what prefixes and arrays are, and their usage scenarios. It is an array obtained by preprocessing the original static array, which can be used to quickly find the sum of a range of the original array.

The meaning of the original array a[i] – the value of the i-th element

The meaning of the prefix of a[i] and the array s[i] – the sum of the first i elements in the array a

As shown in the figure, the upper array is the original array, and the lower array is the prefix and array corresponding to the changed array.

😾3. How to preprocess to get prefix and array

First, we need to know that the prefix and the subscript meaning of the array s s[i] is the sum of the first i elements. Then the meaning of s[i-1] is the sum of the first i-1 elements. At this time, we are based on s[i-1], so we can know:

But pay attention to a problem. Generally, our prefix sum array s[0] must be equal to 0, which means that the sum of the first 0 elements is 0. And it is also to prevent the problem of subscript out of bounds. For example, when i in the formula is equal to 0, out of bounds will occur later.

There is another very important question.

This preprocessing formula is not static, because the first digit of the original array may be subscripted from 0, or it may be subscripted from 1. When the subscript starts from 0, the ith element of the original array is a[i-1], and when the subscript starts from 1, the ith element of the original array is a[i].

So in the case where the subscript of the original array is 1, the formula for finding the prefix sum may also look like this:

Everyone should be flexible.

🎃 4. Use of prefixes and arrays

We got prefix and array by preprocessing, so how to use it?

Let’s start with the meaning of the prefix sum, assuming that we want to get the sum of the xth element to the yth element. The value of s[y] is the sum of the first y elements, and the meaning of s[x-1] is the sum of the first x-1 elements. The difference between the two can get the sum of the xth element to the yth element. and.

The formula is:

This also reflects why the subscript of the prefix sum should start from 1. If it starts from 0, it is easy to cause out-of-bounds problems at x-1.

🍋5. Prefix and template questions practice

1), area and retrieval

Topic Link: Regions and Searches

For the real one-dimensional prefixes and naked questions, we use arr as the prefix and array, preprocess it first, and then use it directly in the function. Note that the subscript of the original array given here starts from 0.        

class NumArray {
    int[] arr;
    public NumArray(int[] nums) {
        int n=nums.length;
        arr=new int[n+1];
        for(int i=0;i<n;i++){
            arr[i+1]=arr[i]+nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return arr[right+1]-arr[left];
    }
}

2), consecutive subarrays and

To analyze the topic, first we need to know the congruence theorem. That is:

If we want to find that the sum of a sub-array is a multiple of k, it means that we need to find two sums of a and b in the prefix sum array that satisfy the above formula, and at the same time ensure that the distance between the two cannot be less than 2 . Since the answer is whether it exists, there is no need to find out the specific sub-array, so we can use set to store the prefix and the value of the remainder of k for each element in the array.

Code conversion:

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n=nums.length;
        if(n<2) return false;
        int[] arr=new int[n+1];
        for(int i=0;i<n;++i){
            arr[i+1]=arr[i]+nums[i];
        }
        Set<Integer> set=new HashSet<>();
        for(int i=2;i<n+1;i++){
            set.add(arr[i-2]%k);
            if (set.contains(arr[i]%k)) return true;
        }
        return  false ;
}
}

3), continuous array

Given a binary array  nums , find   the longest contiguous subarray with the same number of sums, and return the length of that subarray 0 . 1

Topic link: Contiguous array                

Although this question is not a prefix and bare question, it uses the idea of ​​prefix sum. We know that there are only two numbers in the array, 0 and 1. If we use the variable count to record, when we encounter 0, count–, we encounter 1. time count++. If the number of intervals 0 and 1 is the same, then the value of count in these two positions is the same. We use Map to record, the value of count is key, and the subscript is value. When traversing to a certain position, if the count value of a previous position is the same as the current position, it means that the number of 0 and 1 in the two-point interval is the same, and the maximum value of the answer is updated.

class Solution {
    Map<Integer,Integer> map=new HashMap();
    int res=0;
    int count=0;
    public int findMaxLength(int[] a) {
        int n=a.length;
        map.put(0,-1);
        for(int i=0;i<n;++i){
            if(a[i]==0) --count;
            else count++;
            if(map.containsKey(count)){
                res=Math.max(res,i-map.get(count));
            }else{
                map.put(count,i);
            }
        }
        return res;
    }
}

If the article is helpful to you, I hope you can give support to Diansanlian, thank you very much! ! !

Leave a Comment

Your email address will not be published. Required fields are marked *