前缀和数组

一维数组不可变（leetcode303)

思路：这题比较简单，可能第一反应直接遍历，但因为有多组数据，那我们必须要多次调用SumRange函数，时间复杂度O（n)，但如果使用前缀和，即用一个数组preSum记录前n个数之和，这样要计算数组下标[0,2]之间的元素的总和只要用preSum(3)-preSum(0)，时间复杂度降为O（1）

class NumArray {
 private int[] nums;
 public NumArray(int[] nums) {
 this.nums = nums;
 }
 
 public int sumRange(int left, int right) {
 int res = 0;
 for (int i = left; i <= right; i++) {
 res += nums[i];
 }
 return res;
 }
}

class NumArray {
 // 前缀和数组
 private int[] preSum;
 
 public NumArray(int[] nums) {
 // preSum[0] = 0，便于计算累加和
 preSum = new int[nums.length + 1];
 // 计算 nums 的累加和
 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];
 }
}

 二维数组矩阵不可变leetcode304

思路：我们可以维护⼀个⼆维 preSum 数组，专⻔记录以原点为顶点的矩阵的元素之和，就可以⽤⼏次加减运算算出任何⼀个⼦矩阵的元素和 

class NumMatrix {
    
    public static int[][]preSum;
    public NumMatrix(int[][] matrix) {
       int m=matrix.length;
       int n=matrix[0].length;
       if(m==0||n==0) return;
       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-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];
    }
}

 和为k的数组leetcode560

思路：直接记录下有⼏个 preSum[j] 和 preSum[i] - k 相等，直接更新结果，就避免了内层 的 for 循环。我们可以⽤哈希表，在记录前缀和的同时记录该前缀和出现的次数

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n=nums.length;
       HashMappreSum=new HashMap<>();
        preSum.put(0,1);
        int res=0,sum_i=0;
        for(int i=0;i