This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is LeetCode on 303. Area and retrieval – array immutable, difficulty is simple.

Tag: “prefix sum”, “interval sum problem”

Given an integer array nums, find the sum of the elements in the range from index I to j (I ≤ j), including I and j.

Implement NumArray class:

  • NumArray(int[] nums) Initializes an object using the array nums
  • Int sumRange(int I, int j) sumRange(int I, int j) sumRange(int I, int j) sumRange(int I, int j) sumRange(int I, int j) The nums [j]))

Example:

Input: [" NumArray sumRange ", ""," sumRange ", "sumRange"] [[[- 2, 0, 3, 5, 2, 1]], [0, 2], [2, 5], [0, 5]] output: [NULL, 1, -1, -3] NumArray NumArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))Copy the code

Tip:

  • 0 <= nums.length <=
    1 0 4 10^4
  • –
    1 0 5 10^5      <= nums[i] <= 
    1 0 5 10^5
  • 0 <= i <= j < nums.length
  • Call the sumRange method up to $10^4# times

Prefix solution (one dimension)

This is a naked question with prefixes and.

When we need to find the sum of “some section”, we naturally think of “prefix sum”.

The function of prefix sum is to help us quickly find the sum of a certain paragraph, is the reverse operation of “difference”.

Prefixes and arrayssumEach bit of is recorded as the sum of the interval between the current position and the starting position.

Ans = sum[j] -sum [i-1] ans = sum[j] -sum [i-1] ans = sum[j] -sum [i-1]

Since -1 is involved, to reduce some margin processing, we can make the prefix and array index start at 1, and then determine whether the corresponding offset is generated based on whether the source array index starts at 1 when calculating the answer:

class NumArray {
    int[] sum;
    public NumArray(int[] nums) {
        int n = nums.length;
        // Prefixes and array subscripts start at 1, so set length to n + 1 (template part)
        sum = new int[n + 1];
        // Preprocess the prefix and array (template part)
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
    }
    public int sumRange(int i, int j) {
        Sum [j] -sum [i-1] = sum[I, j]
        // But since our source array subscripts start at 0, we do + 1 based on the template
        i++; j++;
        return sum[j] - sum[i - 1]; }}Copy the code
  • Time complexity: Preprocessing prefixes and arrays requires linear scanning of the original array, and the complexity is O(n)O(n)O(n) O(n)O(n)O(1)O(1)O(1) O(1). The overall complexity is O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

One-dimensional prefixes and templates

Let’s sort out the template code of the one-dimensional “prefix and” again:

Preprocessing prefixes and arrays
{    
    sum = new int[n + 1];
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
}

// Calculate [I, j] result
{
    i++; j++;
    ans = sum[j] - sum[i - 1];
}
Copy the code

conclusion

Finally, let’s look at how prefix and relates to other knowledge points.

Why does “prefix sum” greatly reduce the complexity of interval summation? In fact, the essence is to use mathematics to evaluate: the interval sum of a certain segment = the sum from the starting point to the right endpoint of the interval (including the right endpoint) – the sum from the starting point to the left endpoint of the interval (excluding the left endpoint)

The process of solving prefix and array is based on the idea of dynamic programming: because each bit of prefix and sum is to find “the sum of the interval from the current position to the starting position”. Therefore, when solving the prefix sum of a certain digit, we need “the prefix sum of the previous position” and “the original array value of the current position” (regardless of how the prefix sum of the previous position is calculated). The process is similar to the solution process of Fibonacci number of DP introductory question 509.

The last

This is the No.303 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.