前缀和-prefixsum

560. Subarray Sum Equals K Medium

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2 

Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107、

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count=0;
        int[] arr = new int[nums.length+1];
        arr[0]=0;
        for(int i=1;i){
            arr[i]=arr[i-1]+nums[i-1];
        }
        for(int i=0;i){
            for(int j=i+1;j){
                if(arr[j]-arr[i]==k) count++;
            }
        }
        return count;
    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count=0;
        int[] arr = new int[nums.length+1];
        arr[0]=0;
        for(int i=1;i){
            arr[i]=arr[i-1]+nums[i-1];
        }
        Map map  = new HashMap();
        for(int i=0;i){
            count+=map.getOrDefault(arr[i]-k,0);
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        return count;
    }
}

560. Subarray Sum Equals K Medium

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

 Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map map = new HashMap();
        int count = 0;
        int sum=0;
        map.put(0,1);
        for(int i=0;i){
            sum=(sum+nums[i]%k+k)%k;//这里加k是为了防止负数
            count += map.getOrDefault(sum,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;
    }
}

523. Continuous Subarray Sum Medium

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1


class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map map = new HashMap();
        map.put(0,-1);
        int sum=0;
        for(int i=0;i){
            sum=(sum+nums[i]%k)%k;//坑点：这个地方很容易越界，另外注意这个题都是正数
            if(map.get(sum)!=null){
                if(i-map.get(sum)>1) return true;
            }
            else
                map.put(sum,i);
        }
        return false;
    }
}

525. Contiguous Array Medium

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

 Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

class Solution {
    public int findMaxLength(int[] nums) {
        //1.将0 翻为 -1
        for(int i=0;iif(nums[i]==0) nums[i]=-1;
        //2.prefixsum ,记录到map求取长度
        int max = 0;
        Map map = new HashMap();
        map.put(0,-1);
        int sum=0;
        for(int i=0;i){
            sum+=nums[i];
            if(map.get(sum)!=null)    max = Math.max(max,i-map.get(sum)); //如果map中已经存在，说明满足条件，记录最大长度
            else  map.put(sum,i); //如果该sum值还不存在，记录到map
        }
        return max;
    }
}

370. Range Addition Medium

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

Example 1:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

Example 2:

Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0,-4,2,2,2,4,4,-4,-4,-4] 

Constraints:

• 1 <= length <= 105
• 0 <= updates.length <= 104
• 0 <= startIdxi <= endIdxi < length
• -1000 <= inci <= 1000

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        //只在开始位置累加val，在结束位置的下一个位置累减val
        for(int[] update:updates){
            int start = update[0];
            int end = update[1]+1;
            int val = update[2];
            result[start]+=val;
            if(endval;
        }
        //最终做一次prefixsum即为最终结果
        for(int i=1;i){
            result[i]+=result[i-1];
        }
        return result;
    }
}

 304. Range Sum Query 2D - Immutable

Medium

Given a 2D matrix matrix, handle multiple queries of the following type:

• Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

• NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
• int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). 

Example 1:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]

Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle) 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -105 <= matrix[i][j] <= 105
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• At most 104 calls will be made to sumRegion.

class NumMatrix {
    private int[][] result;
    public NumMatrix(int[][] matrix) {
        //这个地方使用[matrix.length+1][matrix[0].length+1] ，是因为后面边界条件容易处理
        result = new int[matrix.length+1][matrix[0].length+1];
        for(int i=0;i){
            for(int j=0;j){
                result[i+1][j+1] = result[i][j+1]+result[i+1][j]-result[i][j]+matrix[i][j];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return result[row2+1][col2+1] - result[row1][col2+1] - result[row2+1][col1] + result[row1][col1];
    }
}

528. Random Pick with Weight Medium

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

• For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

Example 1:

Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.

Example 2:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

Constraints:

• 1 <= w.length <= 104
• 1 <= w[i] <= 105
• pickIndex will be called at most 104 times.

class Solution {

    int[] presum;
    Random random = new Random();
    public Solution(int[] w) {
        presum = new int[w.length];
        for(int i=0;i){
            if(i==0) presum[i]=w[i];
            else presum[i]=presum[i-1]+w[i];
        }
    }
    
    public int pickIndex() {
        int ran = random.nextInt(presum[presum.length-1])+1;//这个地方要+1，因为比如：你是1,5,15,16  那么你取[0,16]总是不包含16，如果不+1 永远取不到16
        int index = Arrays.binarySearch(presum,ran);
        if(index<0) index = -1*(index+1);
        return index;
    }
}