Java前缀和算法题目练习

前缀和

• 前缀和
• 二维前缀和
• 寻找数组的中心下标
• 除自身以外数组的乘积
• 和为k的子数组
• 和可被K整除的子数组
• 连续数组
• 矩阵区域和

前缀和

题目解析：在一个数组中查询起对应区间的和，会查询多次
算法思想：暴力解法：每次查询都进行一次遍历，时间复杂度O(n*m)
前缀和解法：新定义一个数组，每一个下标存放的值是要查询数组的前下标对应值的和，这样我们在访问起某一个区间的时候，直接利用这个数组就非常快速

importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[] args){Scanner in =newScanner(System.in);int n = in.nextInt();int m = in.nextInt();int[] arr =newint[n+1];//此时我们让其下标从1开始，这样可以省略边界问题考虑 arr[0]=0;for(int i =1;i <= n;i++){ arr[i]= in.nextInt();}//题目意思就是给了我们长度是n的数组，但是会有m查询//1.首先定义一个新的数组，其每一个下标对应的值是其从arr1开始到这个下标值的和long[] dp =newlong[n+1];for(int i =1;i <= n;i++){ dp[i]= dp[i -1]+ arr[i];}while(m >0){int l = in.nextInt();int r = in.nextInt();System.out.println(dp[r]- dp[l -1]); m--;}}}

时间复杂度：O(n + m)
空间复杂度：O(n)

二维前缀和

题目解析：和上一题一样，只不过这里变成了二维数组，要求的是对应子矩阵元素之和
前缀和：先定义一个新数组dp，其下标对应的值是原arr 数组[1,1] ~ [i, j]下标的和，此时还是让其下标从1开始这样就不用考虑下标越界情况

importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[] args){Scanner in =newScanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();int m = in.nextInt();int q = in.nextInt();//下标从1开始int[][] arr =newint[n+1][m+1];for(int i =1;i <= n;i++){for(int j =1;j<=m;j++){ arr[i][j]= in.nextInt();}}//前缀和数组long[][] dp =newlong[n+1][m+1];for(int i =1;i<=n;i++){for(int j =1;j<=m;j++){ dp[i][j]= dp[i-1][j]+ dp[i][j-1]+ arr[i][j]- dp[i-1][j-1];}}//使用前缀和数组while(q >0){int x1 = in.nextInt();int y1 = in.nextInt();int x2 = in.nextInt();int y2 = in.nextInt();System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+ dp[x1-1][y1-1]); q--;}}}

时间复杂度：O(n*m + q)
空间复杂度：O(n * m)

寻找数组的中心下标

题目解析：找到一个下标，让其数组左边元素的和等于其右边元素的和
前缀和算法：由于暴力解法每次都要进行遍历多次，这样时间复杂度高
因此我们可以使用f和g两个数组，一个每一个下标用来放其前缀和，一个用来放后缀和，最后遍历一遍判断其f[i] == g[i]即可

classSolution{publicintpivotIndex(int[] nums){int n = nums.length;int[] f =newint[n];int[] g =newint[n];//此时f要从左向右填写，因为后一个要根据前一个填写for(int i =1;i < n;i++){ f[i]= f[i-1]+ nums[i-1];}for(int i = n-2;i >=0;i--){ g[i]= g[i+1]+ nums[i+1];}for(int i =0;i< n;i++){if(f[i]== g[i]){return i;}}return-1;}}

时间复杂度：O(n)
空间复杂度：O(n)

除自身以外数组的乘积

题目解析：返回一个answer数组，里面answer[i]表示的是nums数组中除了num[i]下标的值，其他所有元素的积，返回这个answer数组
前缀积：f表示前缀积，g表示后缀积

classSolution{publicint[]productExceptSelf(int[] nums){int n = nums.length;//一个前缀积和一个后缀积int[] f =newint[n];int[] g =newint[n];int[] ret =newint[n]; f[0]= g[n-1]=1;for(int i =1;i < n;i++){ f[i]= f[i-1]* nums[i-1];}for(int i = n -2;i >=0;i--){ g[i]= g[i+1]* nums[i+1];}for(int i =0; i<n;i++){ ret[i]= f[i]*g[i];}return ret;}}

和为k的子数组

题目解析：数组中找子数组和为k的个数
前缀和：有一个前缀和数组，这样每次我们只要在[ 0 , i-1]找出和为nums[i] - k即可,
但是如果sum[i] == k，此时就要从 [0,-1]中找0，因此可以先将<0,1>放入hash中

classSolution{publicintsubarraySum(int[] nums,int k){Map<Integer,Integer> hash =newHashMap<>(); hash.put(0,1);int sum =0;//表示前缀和int ret =0;for(int num : nums){ sum += num; ret += hash.getOrDefault(sum - k,0);//更新结果 hash.put(sum,hash.getOrDefault(sum,0)+1);//将其放入hash中}return ret;}}

时间复杂度：O(n)
空间复杂度：O(n)

和可被K整除的子数组

题目解析：在一个数组中找出所有子数组和可以整除k的子数组个数
这个题目和上一个求所有和为子数组的个数一样，一些细节处理方式都差不多，唯一不一样的是

classSolution{publicintsubarraysDivByK(int[] nums,int k){Map<Integer,Integer> hash =newHashMap<>();//刚开始要先将0%k放入进去，也就是<0,1>,防止当 hash.put(0% k,1);int sum =0;int ret =0;for(int num : nums){ sum += num;int r =(sum % k + k)%k; ret += hash.getOrDefault( r,0); hash.put(r,hash.getOrDefault(r,0)+1);}return ret;}}

时间复杂度：O(n)
空间复杂度：O(n)

连续数组

题目解析：找一个最长的子数组其和为0，并且此子数组区间中0和1的个数一样
题目转换，我们可以将其中的0看成-1，此时就变成了找出和为0的最长子数组，上面有一个题目是和为k的子数组，此时的k == 0
前缀和 + 哈希表
但是有很多细节不一样，
1.这里哈希表存放的是<前缀和,下标>
2.重复的哈希其不用存放，因为这里要求的是最长子数组
3.长度为i - j
4.<0,-1>,前缀和为0，存放的是-1
5.先使用，后存放入哈希表中

classSolution{publicintfindMaxLength(int[] nums){//此时可以将其0看成-1，此时就变成和为0的最长子数组的求解Map<Integer,Integer> hash =newHashMap<>();//当其[0,i]位置和为0时候，我们要从[0,-1]中找出和为0 hash.put(0,-1);int len =0;int sum =0;for(int i =0;i < nums.length ;i++){if(nums[i]==0){ sum -=1;}else{ sum +=1;}//从前面找和为sum，那后面和就为0，当然其j越靠前越好//因此如果已经有了和为sum，后面的就不用放进去了if(hash.containsKey(sum)){ len =Math.max(len,i - hash.get(sum));}else{//放入hash中 hash.put(sum,i);}}return len;}}

时间复杂度：O(n)
空间复杂度：O(n)

矩阵区域和

题目解析：给了一个二维数组，我们要返回一个相同的二维数组，每一个下标对应的值是其原本二维数组距离其为k的元素所围成的一个矩形中元素之和
前缀和矩阵，上面有一个题目是求(x1,y1) 到 (x2,y2)所围成矩阵的和就用到了前缀和矩阵
因此这里可以先求出前缀和数组，在使用的时候直接根据k求出其是那两个坐标 围成的矩形，有了坐标可以使用前缀和矩阵，这样就求出对应的值了
但是此时要注意其下标是不一样的，前缀和矩阵下标是从1开始

classSolution{publicint[][]matrixBlockSum(int[][] mat,int k){int m = mat.length;int n = mat[0].length;int[][] dp =newint[m+1][n+1];//构建前缀和其下标从1开始for(int i =1;i<= m;i++){for(int j =1;j<= n;j++){ dp[i][j]= dp[i-1][j]+ dp[i][j-1]- dp[i-1][j-1]+ mat[i-1][j-1];}}int[][] ret =newint[m][n];//使用的时候下标也要+1这样才能正常使用前缀和数组for(int i =0;i<m;i++){for(int j =0;j<n;j++){int x1 =Math.max(i-k,0)+1;int y1 =Math.max(j-k,0)+1;int x2 =Math.min(i+k, m -1)+1;int y2 =Math.min(j+k, n -1)+1; ret[i][j]= dp[x2][y2]- dp[x1-1][y2]- dp[x2][y1-1]+ dp[x1-1][y1-1];}}return ret;}}

时间复杂度：O(m * n)
空间复杂度：O(m * n)