303. 区域和检索 (opens new window)

class NumArray {
    int[] preSum;
    public NumArray(int[] nums) {
        int n = nums.length;
        this.preSum = new int[n+1];
        for(int i=1;i<n+1;i++){
            preSum[i] = preSum[i-1]+nums[i-1];
        }
    }
    
    public int sumRange(int left, int right) {
        return preSum[right+1]-preSum[left];
    }
}

304. 二维区域和检索 (opens new window)

class NumMatrix {
    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;i++){
            for(int j=1;j<=n;j++){
                preSum[i][j] = preSum[i][j-1]+preSum[i-1][j]-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[row2+1][col1]-preSum[row1][col2+1]+preSum[row1][col1];
    }
}

396. 旋转函数 (opens new window)

1177. 构建回文串检测 (opens new window)

2559. 统计范围内的元音字符串数 (opens new window)

528. 按权重随机选择 (opens new window)

class Solution {
    int[] preSum;
    int total;
    // w=[3,1,2,4]
    // 划分为[1,3] [4,4] [5,6] [7,10]
    // 第i个区间的左边界为pre[i]-w[i]+1,右边界为pre[i]
    public Solution(int[] w) {
        preSum = new int[w.length];
        preSum[0] = w[0];
        for(int i=1;i<w.length;i++){
            preSum[i] = preSum[i-1]+w[i];
        }
        total = Arrays.stream(w).sum();
    }
    
    public int pickIndex() {
        int x = (int) (Math.random()*total)+1;
        return binarySearch(x);
    }

    int binarySearch(int x){
        int l = 0,r = preSum.length-1;
        while(l<=r){
            int mid = (l+r)>>>1;
            if(preSum[mid]<x)
                l = mid+1;
            else
                r = mid-1;
        }
        return l;
    }
}