前缀和

linwt · linwt · commit 8882d56df5d4 · 2022-02-13T19:01:39.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -31,12 +31,15 @@
 236. 二叉树的最近公共祖先
 283. 移动零
 300. 最长上升子序列
+303. 区域和检索 - 数组不可变
+304. 二维区域和检索 - 矩阵不可变
 338. 比特位计数
 406. 根据身高重建队列
 437. 路径总和
 448. 找到所有数组中消失的数字
 461. 汉明距离
 538. 把二叉搜索树转换为累加树
 543. 二叉树的直径
+560. 和为 K 的子数组
 589. N叉树的前序遍历
 617. 合并二叉树
diff --git a/leetcode_Java/Solution0303.java b/leetcode_Java/Solution0303.java
@@ -0,0 +1,48 @@
+// 区域和检索 - 数组不可变
+
+
+/*
+暴力破解：直接累加计算区间和，时间复杂度O(n)
+ */
+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;
+    }
+}
+
+
+/*
+前缀和：
+1、使用数组存放前缀和，preSum[n] 表示nums数组索引区间 [0, n-1] 的和
+2、计算某个区间元素和，可以直接通过前缀和相减得到，时间复杂度O(1)
+ */
+class NumArray {
+    private int[] preSum;
+
+    public NumArray(int[] nums) {
+        preSum = new int[nums.length + 1];
+        for (int i = 0; i < nums.length; i++) {
+            preSum[i + 1] = preSum[i] + nums[i];
+        }
+    }
+
+    public int sumRange(int left, int right) {
+        return preSum[right + 1] - preSum[left];
+    }
+}
+
+/**
+ * Your NumArray object will be instantiated and called as such:
+ * NumArray obj = new NumArray(nums);
+ * int param_1 = obj.sumRange(left,right);
+ */
diff --git a/leetcode_Java/Solution0304.java b/leetcode_Java/Solution0304.java
@@ -0,0 +1,64 @@
+// 二维区域和检索 - 矩阵不可变
+
+
+/*
+一维前缀和：
+1、初始化时对矩阵的每一行计算前缀和，检索时对二维区域中的每一行计算子数组和，然后对每一行的子数组和计算总和。
+2、preSum[n][m] 表示矩阵matrix 左上角为(n, 0) 右下角为 (n, m-1) 的子矩形范围元素和
+3、preSum 初始化时比 matrix 多了一列，用于初始化前缀和矩阵首列为0
+4、检索的时间复杂度是 O(m)
+ */
+class NumMatrix {
+    private int[][] preSum;
+
+    public NumMatrix(int[][] matrix) {
+        int n = matrix.length, m = matrix[0].length;
+        preSum = new int[n][m + 1];
+        for (int row = 0; row < n; row++) {
+            for (int col = 0; col < m; col++) {
+                preSum[row][col + 1] = preSum[row][col] + matrix[row][col];
+            }
+        }
+    }
+
+    public int sumRegion(int row1, int col1, int row2, int col2) {
+        int res = 0;
+        for (int i = row1; i <= row2; i++) {
+            res += preSum[i][col2 + 1] - preSum[i][col1];
+        }
+        return res;
+    }
+}
+
+
+
+/*
+二维前缀和：
+1、preSum[n][m] 表示矩阵matrix 左上角为(0, 0) 右下角为 (n-1, m-1) 的子矩形范围元素和
+2、preSum 初始化时比 matrix 多了一行一列，用于初始化前缀和矩阵首行首列为0
+3、前缀和矩阵元素填充、计算子矩形元素和，都是通过其他子矩形的面积加减得到
+4、检索的时间复杂度是 O(1)
+ */
+class NumMatrix {
+    private int[][] preSum;
+
+    public NumMatrix(int[][] matrix) {
+        int n = matrix.length, m = matrix[0].length;
+        preSum = new int[n + 1][m + 1];
+        for (int row = 1; row <= n; row++) {
+            for (int col = 1; col <= m; col++) {
+                preSum[row][col] = preSum[row - 1][col] + preSum[row][col - 1] - preSum[row - 1][col -1] + matrix[row - 1][col - 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];
+    }
+}
+
+/**
+ * Your NumMatrix object will be instantiated and called as such:
+ * NumMatrix obj = new NumMatrix(matrix);
+ * int param_1 = obj.sumRegion(row1,col1,row2,col2);
+ */
diff --git a/leetcode_Java/Solution0560.java b/leetcode_Java/Solution0560.java
@@ -0,0 +1,68 @@
+// 和为 K 的子数组
+
+
+/*
+暴力破解：两层for循环遍历判断所有子数组
+ */
+class Solution {
+    public int subarraySum(int[] nums, int k) {
+        int n = nums.length, count = 0;
+        for (int end = 0; end < n; end++) {
+            int sum = 0;
+            for (int start = end; start >= 0; start--) {
+                sum += nums[start];
+                if (sum == k) {
+                    count++;
+                }
+            }
+        }
+        return count;
+    }
+}
+
+
+/*
+前缀和 + 暴力破解
+ */
+class Solution {
+    public int subarraySum(int[] nums, int k) {
+        int n = nums.length, count = 0;
+        int[] preSum = new int[n + 1];
+        for (int i = 0; i < n; i++) {
+            preSum[i + 1] = preSum[i] + nums[i];
+        }
+        for (int end = 1; end <= n; end++) {
+            for (int start = 0; start < end; start++) {
+                if (preSum[end] - preSum[start] == k) {
+                    count++;
+                }
+            }
+        }
+        return count;
+    }
+}
+
+
+/*
+前缀和 + 哈希表：
+1、使用HashMap存放 <前缀和, 出现次数>
+2、由于前缀和通过HashMap获取，不用在数组中获取，因此用一个变量记录当前前缀和即可
+3、由于 pre[end] - pre[start - 1] = k 则 pre[end] - k = pre[start - 1]
+  遍历数组，边累加计算当前前缀和，并判断另一个预期的前缀和是否出现在HashMap中，以及出现次数，可以构成和为 k 的连续子数组，累加个数
+4、累加记录当前前缀和及次数到HashMap中
+ */
+class Solution {
+    public int subarraySum(int[] nums, int k) {
+        Map<Integer, Integer> map = new HashMap<>();
+        map.put(0, 1);
+        int curPreSum = 0, count = 0;
+        for (int i = 0; i < nums.length; i++) {
+            curPreSum += nums[i];
+            if (map.containsKey(curPreSum - k)) {
+                count += map.get(curPreSum - k);
+            }
+            map.put(curPreSum, map.getOrDefault(curPreSum, 0) + 1);
+        }
+        return count;
+    }
+}
