303. 区域和检索 - 数组不可变

图片.png

由于需要多次调用获取区间和，因此可以预先计算好前缀和，这样一来在获取区间和时就可以将时间复杂度降低至O(1)

  1. class NumArray {
  2.     int preSum[];
  3.     public NumArray(int[] nums) {
  4.         //推荐将前缀和数组大小设置为nums.length+1
  5.         //preSum[i]表示num[0]-nums[i-1]的元素累加和
  6.        preSum=new int[nums.length+1];
  7.         preSum[0]=nums[0];
  8.         for(int i=1;i<=nums.length;i++)
  9.             preSum[i]=nums[i-1]+preSum[i-1];
  11.     }
  14.     public int sumRange(int left, int right) {
  15.       //preSum[right+1]-->nums[0]-nums[rihht]  preSum[left]-->nums[0]-nums[left-1]
  16.       //二者之差就是nums[left]-nums[right]
  17.         return preSum[right+1]-preSum[left];
  19.     }
  20. }

304. 二维区域和检索 - 矩阵不可变

图片.png

题目的意思是给定左上角和右下角的的坐标，然后计算以左上角和右下角构成区域内元素之和

图片.png
以这个为例，红色区域元素之和=绿色区域元素之和-蓝色区域之和-黄色区域之和+粉色区域元素之和
以横向为x轴，纵向为y轴，最左上角为(0,0)
假设我们已经有前缀和数组preSum[x][y]: 表示（0，0）->(x-1,y-1)区域内的元素之和
则给定任意给出的左上角（x1,y1) 右上角（x2,y2)
sum=preSum(x2+1,y2+1)-preSum[x1][y2+1]-preSum[x2+1][y1]+preSum[x1][y1]

  1. class NumMatrix {
  2.     int [][]preSum;
  3.     public NumMatrix(int[][] matrix) {
  4.         int m=matrix.length;
  5.         int n=matrix[0].length;
  6.         preSum=new int[m+1][n+1];
  7.         for(int i=1;i<=m;i++)
  8.         {
  9.             for(int j=1;j<=n;j++)
  10.             {
  11.                 //二维前缀和的计算方法
  12.                 preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+matrix[i-1][j-1];
  13.             }
  14.         }
  16.     }
  18.     public int sumRegion(int row1, int col1, int row2, int col2) {
  19.         return preSum[row2+1][col2+1]-preSum[row1][col2+1]-preSum[row2+1][col1]+preSum[row1][col1];
  21.     }
  22. }

560. 和为 K 的子数组

图片.png

  1. 前缀和+暴力搜索

先记录前缀和，然后再二重for循环比较是否有前缀和之差是k

  1. class Solution {
  2.     public int subarraySum(int[] nums, int k) {
  3.         int [] preSum=new int[nums.length+1];
  4.         for(int i=1;i<preSum.length;i++)
  5.             preSum[i]=preSum[i-1]+nums[i-1];
  6.         int ans=0;
  7.         for(int i=1;i<preSum.length;i++)
  8.         {
  9.             for(int j=1;j<=i;j++)
  10.             {
  11.                 if(preSum[i]-preSum[j-1]==k)
  12.                     ans++;
  13.             }
  14.         }
  15.         return ans;
  16.     }
  17. }
  18. //O(n^2)
  19. //O(n)

  1. 前缀和+map优化

    使用一个map来记录各个前缀和对应的个数，假设遍历到当前位置的前缀和是sum,如果之前位置的前缀和存在sum-k则说明出现了连续区间内的元素和为k的情况

    1. class Solution {
    2.  public int subarraySum(int[] nums, int k) {
    3.      HashMap<Integer,Integer> map=new HashMap<>();
    4.      int sum1=0;
    5.      int ans=0;
    6.      map.put(0,1);//base 条件 不能省略比如 1 1 1 k=2  当sum1=1+1=2时 对应的sum2=0  此时前缀和为0需要出现1次
    7.      //没有map.put(0,1)的话此时这种情况就会没有被记录
    8.      for(int i=0;i<nums.length;i++)
    9.      {
    10.          //sum1=nums[0]-nums[i]的累加和
    11.          sum1+=nums[i];
    12.          int sum2=sum1-k;//sum1-sum2=k
    13.          //如果这个sum2存在 则sum2-sum1=k  这个区间内的和是k 但是sum2可能不止1个  
    14.          //比如1 -1 1 -1 1 -1..... 前缀和为0的就有好几个
    15.          if(map.containsKey(sum2))
    16.              ans+=map.get(sum2);
    17.          //将当前遍历到的位置的前缀和记录进map
    18.          map.put(sum1,map.getOrDefault(sum1,0)+1);
    20.      }
    21.      return ans;
    22.  }
    23. }
    24. //O(n)
    25. //O(n)