Prefix and array series

It involves three questions ：
303. Area and retrieval - The array is immutable
304. Two dimensional region and retrieval - The matrix is immutable
560. And for K Subarray

If you want to get 「 Interval and 」, The easiest way to think of is to traverse the desired interval , Add circularly . If there are many such needs , here , The time complexity is O(n^2)
Based on the scenario described above , We can use it 「 The prefix and 」 Optimize , The prefix and the value of each element in the array are interval [0…i] Elements and .

Be careful ：
Prefixes and apply to invariant arrays ; For changing arrays , have access to 「 Line segment tree 」, The detailed introduction of segment tree can be seen Line tree details
Area and retrieval - The array is immutable

Area and retrieval - The array is immutable

Details of the topic can be seen ： Area and retrieval - The array is immutable

Suggest ：preSum[] Overall backward offset by one bit , Simple handling

If we find the interval [2,4] And , Just calculate preSum[4 + 1] - preSum[2] that will do

Code ：

class NumArray {
    
    //  Record an array of prefixes and 
    private int[] preSum;
    public NumArray(int[] nums) {
    
        // preSum  from  1  Start , Avoid cross-border problems 
        preSum = new int[nums.length + 1];
        for (int i = 1; i < preSum.length; i++) {
    
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    public int sumRange(int left, int right) {
    
        return preSum[right + 1] - preSum[left];
    }
}

Two dimensional region and retrieval - The matrix is immutable

Details of the topic can be seen ： Two dimensional region and retrieval - The matrix is immutable

If you sum the red intervals , Demand only preSum[4,4] - preSum[1,4] - preSum[4,1] + preSum[1,1] that will do
● preSum[4,4]： yellow + blue + green + red
● preSum[1,4]： yellow + blue
● preSum[4,1]： yellow + green
● preSum[1,1]： yellow

Code ：

class NumMatrix {
    
    private int[][] preSum;
    public NumMatrix(int[][] matrix) {
    
        int m = matrix.length;
        int n = matrix[0].length;
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i < m + 1; i++) {
    
            for (int j = 1; j < n + 1; j++) {
    
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
    
        return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
    }
}

And for K Subarray

Details of the topic can be seen And for K Subarray
reference 「 Sum of two numbers 」 The idea of , utilize HashMap.

Code ：

public int subarraySum(int[] nums, int k) {
    

    Map<Integer, Integer> preSum = new HashMap<>();
    preSum.put(0, 1);

    int sum = 0;
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
    
        sum += nums[i];
        int target = sum - k;
        if (preSum.containsKey(target)) res += preSum.get(target);
        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
    }
    return res;
}