前缀和思想的理解与运用
前缀和通常用于解决 数组中和满足一定条件的子数组问题
将原来可能需要O(n*n)双重循环遍历子数组的问题简化到O(n)
可以尝试用以下思路解决：
根据前缀和构造出符合题意的公式，区间[x,y]，p(x)和p(y)之间满足什么关系
如：
- 长度最小的子数组：存在公式 p(y)-p(x)>=target，即在确定p(x)的情况下 p(x)+target<=p(y)，找到大于等于p(x)+target的最小值
- 和为 K 的子数组：存在公式 p(y)-p(x)=k，即在确定p(y)的情况下 p(y)-k=p(x)，找到等于p(y)-k的值
构造前缀和
-
如何构造一维数组的前缀和数组
通常声明的前缀和数组比原数组长一位，用于表示的是前n-1项的前缀和
然后+1才能表示含有当前项的结果
int[] prefix; public LeetCode303(int[] nums) { // 前缀和，记录前n-1项之和 prefix = new int[nums.length + 1]; for (int i = 1; i <= nums.length; i++) { prefix[i] = prefix[i - 1] + nums[i - 1]; } } public int sumRange(int left, int right) { // 最后结果就是 前right项减前left-1项 return prefix[right + 1] - prefix[left]; } -
构造二维数组的前缀和，还是当比原长度都多加一位
然后+1才能表示含有当前行（列）的结果
int[][] prefix; public LeetCode304(int[][] matrix) { int row = matrix.length; int col = matrix[0].length; // 构造前缀和数组的时候，数组长度加一位，然后都取n-1项，可以避免为0的判断 prefix = new int[row + 1][col + 1]; for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { // 加两次多加了一次prefix[i - 1][j - 1] prefix[i][j] = matrix[i - 1][j - 1] + prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { // 注意加不加1的情景：不加1不包括当前行（列）的结果 // 求子矩阵的面积 return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1]; }
经典前缀和
-
区间[x,y]，前缀和数组p存在公式：
p(y)-p(x)>=target，即在确定p(x)的情况下，存在 p(x)+target<=p(y)，找到大于等于p(x)+target的最小值
因为都是正数，所以前缀和数组也是递增的，可以使用二分查找
前缀和+二分查找
/* 求和大于等于target的子数组 因为都是正数，所以前缀和数组也是递增的，所以在前缀和数组p中寻找p[y]>=p[x]+target的最小值，可以使用二分查找 二分查找时间复杂度 logn */ public int minSubArrayLen(int target, int[] nums) { int len = nums.length; int[] prefix = new int[len + 1]; int ans = len + 1; for (int i = 1; i <= len; i++) { prefix[i] = prefix[i - 1] + nums[i - 1]; } for (int x = 0; x <= len; x++) { int k = prefix[x] + target; int location = binary(prefix, k); if (location > 0) { ans = Math.min(ans, location - x); } } return ans == len - 1 ? 0 : ans; } // 有序数组二叉查找大于等于k的最小下标 private int binary(int[] prefix, int k) { int left = 0, right = prefix.length - 1; while (left <= right) { int mid = (left + right) / 2; if (prefix[mid] > k) { right = mid - 1; } else if (prefix[mid] < k) { left = mid + 1; } else { return mid; } } // 返回左下标即可 return left >= prefix.length ? -1 : left; } -
区间[x,y]，前缀和数组p存在公式：
(p(y)-p(x))对k取模等于0，根据同余定理，存在p(y)对k取模=p(x)对k取模
因为都是正数，所以跟取余结果一样，即存在p(y)%k=p(x)%k
等于关系使用hashmap
前缀和+hashmap
public boolean checkSubarraySum(int[] nums, int k) { int len = nums.length; int[] prefix = new int[len + 1]; for (int i = 1; i <= len; i++) { prefix[i] = prefix[i - 1] + nums[i - 1]; } // 需要寻找前缀和数组p，(p[y]-p[x])%k=0，根据同余定理，即y%k等于x%k，即寻找两个数他们对k的取余一样 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i <= len; i++) { int mod = prefix[i] % k; if (map.containsKey(mod)) { if (i - map.get(mod) >= 2) return true; } else { // 只有在不含有该余数的时候才put（即余数一样的情况下，需要留下标最小的） map.put(mod, i); } } return false; } -
类似于【LeetCode523连续的子数组和】，不同点在于原数组中含有负数
在Java中a%b，取余操作，当a小于0的时候，结果小于0，跟取模不同；如-8%5=-3，但是-8对5取模等于2
- 可以使用Math.floorMod(a,b)计算a与b的取模结果
- (a%b+b)%b等于取模结果
前缀和+hashmap
public int subarraysDivByK(int[] nums, int k) { // 子数组和是k的整数倍，即针对前缀和数组p，存在(p(y)-p(x))对k取模=0 // 根据同余定理，即p(y)对k取模等于p(x)对k取模 // 注意在Java中a%b，取余操作，当a小于0的时候，结果小于0，跟取模不同；如-8%5=-3，但是-8对5取模等于2 // 1. 可以使用Math.floorMod(a,b)计算a与b的取模结果 // 2. (a%b+b)%b等于取模结果 int ans = 0, sum = 0; Map<Integer, Integer> map = new HashMap<>(); // 隐式前缀和+map(0,1) map.put(0, 1); for (int i = 0; i < nums.length; i++) { sum += nums[i]; int mod = (sum % k + k) % k; int count = map.getOrDefault(mod, 0); ans += count; map.put(mod, count + 1); } return ans; } -
区间[x,y]，前缀和数组p存在公式：
p(y)-p(x)=k，在确定p(y)的情况下，p(y)-k=p(x)
等于关系使用hashmap
前缀和+hashmap
public int subarraySum(int[] nums, int k) { // 不直接显式的声明一个前缀和数组，用一个变量隐式的表示前缀和 Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); int sum = 0, ans = 0; for (int num : nums) { sum += num; // p[y]-p[x]=k，则y-x为符合条件的区间 int count = map.getOrDefault(sum - k, 0); ans += count; // 更新当前值出现的次数 map.put(sum, map.getOrDefault(sum, 0) + 1); } return ans; } -
与【LeetCode560和为 K 的子数组】一样
区间[x,y]，前缀和数组p存在公式：
p(y)-p(x)=goal，在确定p(y)的情况下，p(y)-goal=p(x)
等于关系使用hashmap
前缀和+hashmap
public int numSubarraysWithSum(int[] nums, int goal) { int sum = 0, ans = 0; Map<Integer, Integer> map = new HashMap<>(); // 需要先预设 前缀和等于0的有一个 map.put(0, 1); // 前缀和p(y)-goal=p(x)，则区间x-y和为goal for (int i = 0; i < nums.length; i++) { sum += nums[i]; int count = map.getOrDefault(sum - goal, 0); ans += count; map.put(sum, map.getOrDefault(sum, 0) + 1); } return ans; } -
区间[x,y]，前缀和数组p存在公式：
2*(p(y)-p(x))=y-x
p(y)-p(x)必然是1的数目 等于y-x的一半则1和0数目相等各占一半
稍加转换即 2p(x)-x=2p(y)-y，即在前缀和数组中寻找2i-i相等的点，其间隔最大，可使用hashmap记录前缀和+hashmap
public int findMaxLength(int[] nums) { // 前缀和找公式，要想满足数组中0和1一样多的子数组，计算前缀和数组p // 存在 2*(p[y]-p[x])=y-x // p[y]-p[x]必然是1的数目 等于y-x的一半则1和0数目相等各占一半 // 稍加转换即 2p[x]-x=2p[y]-y，即在前缀和数组中寻找2i-i相等的点，其间隔最大，可使用hashmap记录 int length = nums.length; int[] prefix = new int[length + 1]; for (int i = 1; i <= length; i++) { prefix[i] = prefix[i - 1] + nums[i - 1]; } Map<Integer, Integer> map = new HashMap<>(); int ans = 0; for (int i = 0; i <= length; i++) { int num = 2 * prefix[i] - i; if (map.containsKey(num)) { ans = Math.max(ans, i - map.get(num)); } else { map.put(num, i); } } return ans; } -
这题归属到动态规划和分治下面的，但是对于子数组和的问题也一样可以使用前缀和思路解决
且最终消耗时间和动态规划一样 1ms击败100%思路：
前缀和数组p，求 p(y)-p(x)的最大值，在p(y)固定的情况下，使p(x)最小即可
可通过维护一个最小值min来表示y前面的最小值public int maxSubArray(int[] nums) { int ans = Integer.MIN_VALUE, sum = 0, min = 0; for (int num : nums) { sum += num; ans = Math.max(ans, sum - min); min = Math.min(sum, min); } return ans; } -
应用前缀和的一道困难题：
区间[x,y]，前缀和数组p存在公式：
p(y)-p(x)>=target，即在确定p(x)的情况下，存在 p(x)+target<=p(y)，找到大于等于p(x)+target的最小值
与【LeetCode209长度最小的子数组】不同的是，原数组中存在负数，前缀和数组非单调递增，所以不能使用二分查找寻找大于等于p(x)+k的最小值，如果暴力查找的话，最后总的时间复杂度达到O(n*n)
优化的解法方案是使用单调队列：
因为使用前缀和以及求最小长度，所以有以下特性： 1. x2>x1，但是p[x2]<p[x1]，说明x1到x2之间和为负值，所以在x1满足和y的区间和大于k的情况下，x2必满足，所以再计算最小长度的情况下可以舍弃x1 即遍历前缀和数组的时候，发现p[x]比已有的前缀和大，可以直接丢弃已有的前缀和 2. 当x满足和y的区间和大于等于k，及时再有y1、y2与x满足，因为求的是最小长度所以也无需计算了， 即x计算得到一次结果之后，就可以舍弃了 使用单调队列，可以满足上面的两个特性，当新遍历得到的元素大于队尾最大的元素，则移出队尾元素，不停的重复上面的动作，最后将他放到队尾 寻找小于等于p[y]-k的，则可以从队列头部开始寻找，队列头部开始是最小的然后单调递增 因为最后需要计算长度，所以单调队列存储前缀和数组的下标前缀和+单调队列
/* 不同于 LeetCode209长度最小的子数组 因为存在负数的缘故 不满足单调性 这里不能使用类似的滑动窗口的办法（扩大窗口求和、满足条件开始缩小窗口....） 求子数组和的问题 还有一种常用解法：前缀和：前n项之和 如：求子数组和等于target的个数：前缀和+map 求子数组和大于等于target的最小长度：前缀和+单调队列 前缀和数组p，如果p[y]-p[x]>=k，则区间[x,y)和满足大于等于k 换言之，在y固定的情况下，寻找p[x]<=p[y]-k，比p[y]-k小的都满足条件 暴力解法就是遍历p数组，每次确定一个y之后，在y前面寻找是否有比p[y]-k小的 时间复杂度 n*n 优化的解法方案是使用单调队列： 因为使用前缀和以及求最小长度，所以有以下特性：（k>0） 1. x2>x1，但是p[x2]<p[x1]，说明x1到x2之间和为负值，所以在x1满足和y的区间和大于k的情况下，x2必满足，所以再计算最小长度的情况下可以舍弃x1 即遍历前缀和数组的时候，发现p[x]比已有的前缀和大，可以直接丢弃已有的前缀和 2. 当x满足和y的区间和大于等于k，及时再有y1、y2与x满足，因为求的是最小长度所以也无需计算了， 即x计算得到一次结果之后，就可以舍弃了 使用单调队列，可以满足上面的两个特性，当新遍历得到的元素大于队尾最大的元素，则移出队尾元素，不停的重复上面的动作，最后将他放到队尾 寻找小于等于p[y]-k的，则可以从队列头部开始寻找，队列头部开始是最小的然后单调递增 因为最后需要计算长度，所以单调队列存储前缀和数组的下标 */ public int shortestSubarray(int[] nums, int k) { int len = nums.length; long[] prefix = new long[len + 1]; // 构造前缀和数组 for (int i = 1; i <= len; i++) { // 如果有大于等于k的直接返回结果1 if (nums[i - 1] >= k) { return 1; } prefix[i] = prefix[i - 1] + (long) nums[i - 1]; } Deque<Integer> deque = new LinkedList<>(); int ans = len + 1; for (int y = 0; y < len + 1; y++) { // 寻找满足的值，找到并移除 while (!deque.isEmpty() && prefix[deque.peekFirst()] <= prefix[y] - k) { ans = Math.min(ans, y - deque.pollFirst()); } // x2>x1，但是p[x2]<p[x1]，说明x1到x2之间和为负值，所以在x1满足和y的区间和大于k的情况下，x2必满足，所以再计算最小长度的情况下可以舍弃x1 while (!deque.isEmpty() && prefix[deque.peekLast()] >= prefix[y]) { deque.pollLast(); } deque.addLast(y); } return ans == len + 1 ? -1 : ans; } -
求二叉树中任意路径和等于目标值
类似于数组，求子数组等于目标值的个数，也可以使用前缀和
// 求路径中子路径和等于目标和，可以使用前缀和 // 前缀和：前n项之和；若节点j的前缀和=当前节点i前缀和-target，则节点j到节点i的路径和等于target // 通过map保存前缀和出现的次数 public int pathSum(TreeNode root, int targetSum) { Map<Integer, Integer> prefix = new HashMap<>(); // 前缀和为0的有一个 prefix.put(0, 1); return pathSum(root, prefix, targetSum, 0); } private int pathSum(TreeNode root, Map<Integer, Integer> prefix, int targetSum, int curr) { if (root == null) return 0; // 当前前缀和 curr += root.val; int ans = prefix.getOrDefault(curr - targetSum, 0); // 将当前前缀和放入map，之前若有该前缀和，则数量累计+1 prefix.put(curr, prefix.getOrDefault(curr, 0) + 1); ans += pathSum(root.left, prefix, targetSum, curr); ans += pathSum(root.right, prefix, targetSum, curr); // 回溯，将当前前缀和从map中移除 prefix.put(curr, prefix.get(curr) - 1); return ans; }
前缀和在随机抽样中的应用
-
如何随机选择带有权重的各个点，并且使得被选择到的概率一样
构造前缀和数组p，找到p(y)>=随机数x的最小值
前缀和+二分查找
/* 输入多个矩形，要求输出一个随机点，该点必须落在输入的多个矩形中 要求所有矩形中的点被选取到的概率一样 各个矩形被选择到的概率取决于他们整点数目的大小，设第i个矩形中有w(i)个整点、所有矩形中整点数目sum，则该矩形应该被选择到的概率为 w(i)/sum 如何选择某个矩形，可以考虑构造矩形整点数目的前缀和，如果前缀和数组p，找到p[y]>=随机数x的最小值y，则可以认为选择到了第y-1个矩形 举个例子：矩形整点数分别为 3 8 5 12 前缀和数组为 0 3 11 16 28 产生一个28以内的随机数x=20，大于等于x的最小值是28（y=4），则选择第y-1个矩形 前缀和是有序数组，有序数组查找使用二分法 确定好了选择第i个矩形之后，再确定选择矩形i中的某一个点 1. 再次生成横坐标随机值、纵坐标随机值，确定一个数（坐标） 2. 利用刚才生成的随机数x，b=x-p[y-1] 则为在第y-1个矩形中第b个点（） 在确定第b个点的横纵坐标，横坐标= x-base + b/height (走了几个轮回height) 纵坐标= y-base + b%height（走了几步height） 这里的b需要减1，（一共九个点，标号需要是从0-8）不然计算坐标偏移量的时候会产生超出的误差 */ int[] prefix; int[][] rects; Random random; int length; public LeetCode497(int[][] rects) { this.rects = rects; length = rects.length; prefix = new int[length + 1]; for (int i = 1; i <= length; i++) { int num = (rects[i - 1][2] - rects[i - 1][0] + 1) * (rects[i - 1][3] - rects[i - 1][1] + 1); prefix[i] = prefix[i - 1] + num; } random = new Random(); } public int[] pick() { int[] ans = new int[2]; int x = random.nextInt(prefix[length]) + 1; // 第y-1个矩形 int y = binarySearch(prefix, x); int location = x - prefix[y - 1]; // 构造矩形中的整点坐标 int height = rects[y - 1][3] - rects[y - 1][1] + 1; // location-1表示该矩形内的第几个点的位置 ans[0] = rects[y - 1][0] + (location - 1) / height; ans[1] = rects[y - 1][1] + (location - 1) % height; return ans; } private int binarySearch(int[] prefix, int x) { int left = 0, right = prefix.length - 1; while (left <= right) { int mid = (left + right) >> 1; if (prefix[mid] > x) { right = mid - 1; } else if (prefix[mid] < x) { left = mid + 1; } else { return mid; } } return left; } -
同【LeetCode497非重叠矩形中的随机点】
随机选择带有权重的点
前缀和+二分查找
int[] prefix; Random random; int length; public LeetCode528(int[] w) { length = w.length; prefix = new int[length + 1]; for (int i = 1; i <= length; i++) { prefix[i] = prefix[i - 1] + w[i - 1]; } random = new Random(); } public int pickIndex() { // 生产随机[1,prefix[len]]之间的随机数 int num = random.nextInt(prefix[length]) + 1; // 二分查找，大于等于该随机数的最小值 int location = Arrays.binarySearch(prefix, num); if (location < 0) { return -location - 2; } else { return location - 1; } }
```java Arrays.binarySearch() 能找到等于的值 返回该索引位置（大于0） 找不到返回的是 -插入点-1 （-insertion point-1）（小于0） ```
总结
- 使用前缀和关键在于能不能找到相应的关系，然后再选用合适的算法或数据结构
评论 (0)
