【面试算法笔记】0106-数组-区间和

个人主页https://github.com/zbhgis前言本系列主要记录自己学习算法的过程中的感悟。力扣303. 区域和检索-数组不可变链接https://leetcode.cn/problems/range-sum-query-immutable/description/注意点通过计算出前缀和数组来快速找到对应区间的和。代码class NumArray { private static int[] s; public NumArray(int[] nums) { s new int[nums.length 1]; for (int i 0; i nums.length; i ) s[i 1] s[i] nums[i]; } public int sumRange(int left, int right) { return s[right 1] - s[left]; } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj new NumArray(nums); * int param_1 obj.sumRange(left,right); */时空复杂度分析单层循环需要遍历n次因此时间复杂度为O(n)空间复杂度为O(1)Acwing795. 前缀和链接https://www.acwing.com/problem/content/797/注意点同上这一题要注意给出的查询值不是下标。代码import java.util.Scanner; public class Main { private static int[] s; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[] nums new int[n]; for (int i 0; i n; i ) { nums[i] sc.nextInt(); } s new int[n 1]; for (int i 0; i n; i ) { s[i 1] s[i] nums[i]; } for (int i 0; i m; i ) { int l sc.nextInt(); int r sc.nextInt(); System.out.println(getRes(l, r)); } } private static int getRes(int left, int right) { return s[right] - s[left - 1]; } }时间复杂度分析同上力扣 304.二维区域和检索-矩阵不可变链接https://leetcode.cn/problems/range-sum-query-2d-immutable/description/注意点类似上一题这回的难点在于怎么构造前缀和以及二维前缀和如何相减。最好画个图前者就是三个小矩形相加再减去重复部分后者其实就是大矩形减去一条长边一条宽边再加上多减的区域。代码class NumMatrix { private final int[][] sum; public NumMatrix(int[][] matrix) { int m matrix.length; int n matrix[0].length; sum new int[m 1][n 1]; for (int i 0; i m; i) { for (int j 0; j n; j) { sum[i 1][j 1] sum[i 1][j] sum[i][j 1] - sum[i][j] matrix[i][j]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return sum[row2 1][col2 1] - sum[row2 1][col1] - sum[row1][col2 1] sum[row1][col1]; } } /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix obj new NumMatrix(matrix); * int param_1 obj.sumRegion(row1,col1,row2,col2); */时空复杂度分析双层循环因此时间复杂度为O(m*n)空间复杂度为O(1)Acwing796. 子矩阵的和链接https://www.acwing.com/problem/content/798/注意点同上这一题也要注意给出的查询值不是最终下标。代码import java.util.Scanner; public class Main { private static int[][] sum; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int q sc.nextInt(); sum new int[n 1][m 1]; for (int i 0; i n; i ) { for (int j 0; j m; j ) { sum[i 1][j 1] sum[i 1][j] sum[i][j 1] - sum[i][j] sc.nextInt(); } } for (int i 0; i q; i ) { int row1 sc.nextInt() - 1; int col1 sc.nextInt() - 1; int row2 sc.nextInt() - 1; int col2 sc.nextInt() - 1; System.out.println(getRes(row1, col1, row2, col2)); } } private static int getRes(int row1, int col1, int row2, int col2) { return sum[row2 1][col2 1] - sum[row2 1][col1] - sum[row1][col2 1] sum[row1][col1]; } }时空复杂度分析同上参考https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html