LeetCode-刷题记录-前缀和合集（本篇blog会持续更新哦~）

一、前缀和（Prefix Sum）算法概述

前缀和算法通过预先计算数组的累加和，可以在常数时间内回答多个区间和相关的查询问题，是解决子数组和问题中的重要工具。

它的基本思想是通过预先计算和存储数组的前缀和，可以在 O(1) 的时间复杂度内计算任意子数组的和。

1. 定义：
   • 对于数组 nums，其前缀和 prefix[i] 定义为从数组起始位置到第 i 个元素的累加和。

• 具体公式：prefix[i] = nums[0] + nums[1] + ... + nums[i]。

2. 计算方法：
   • 首先，创建一个额外的数组或哈希表，用来存储每个位置的前缀和。
   • 通过一次遍历数组，依次计算并填充这个数组或哈希表。

3. 应用：
   • 快速计算子数组和：通过前缀和，可以快速计算任意子数组的和。例如，子数组 nums[l...r] 的和可以通过 prefix[r] - prefix[l-1] 来计算，其中 l 和 r 分别是子数组的左右边界。

• 解决相关问题：例如，最大子数组和、和为特定值的子数组个数等问题，都可以通过前缀和算法高效解决。

---

二、前缀和习题合集

1. LeetCode 930 和相同的二元子数组

• 思路：

假设原数组的前缀和数组为 sum，且子数组 (i,j] 的区间和为 goal，那么 sum[j]−sum[i]=goal。因此我们可以枚举 j ，每次查询满足该等式的 i 的数量。

用哈希表记录每一种前缀和出现的次数，假设我们当前枚举到元素 nums[j]，我们只需要查询哈希表中元素 sum[j]−goal 的数量即可，这些元素的数量即对应了以当前 j 值为右边界的满足条件的子数组的数量。

• pre[j] - pre[i]= goal —> pre[i] = pre[j] - goal

• 如果存在前缀和为 pre[j] - goal(也就是pre[i])

• 说明从某个位置 j 到当前位置 i 的子数组和为 goal

最后这些元素的总数量即为所有和为 goal 的子数组数量。

• 代码：

class Solution {public int numSubarraysWithSum(int[] nums, int goal) {int n = nums.length; // 数组的长度Map<Integer,Integer> map = new HashMap<>(); // 使用哈希表来记录前缀和的出现次数int pre_J = 0; // 初始前缀和为0int ans = 0; // 计数器，用来记录符合条件的子数组个数for (int i = 0; i < n; i++) {map.put(preJ, map.getOrDefault(pre_J, 0) + 1); // 更新前缀和为 preJ 的出现次数pre_J += nums[i]; // 计算当前位置的前缀和//pre[j] - pre[i]= goal //pre[i] = pre[j] - goal// 计算满足条件的子数组个数// 如果存在前缀和为 pre[j] - goal(也就是pre[i])//说明从某个位置 j 到当前位置 i 的子数组和为 goalans += map.getOrDefault(pre_J - goal, 0);}return ans; // 返回符合条件的子数组个数}
}

---

2. LeetCode 560 和为K的子数组

• 这里咋一看好像是可以用滑动窗口哈 ，但是发现数据里有负数。因为nums[i]可以小于0，也就是说右指针j向后移1位不能保证区间会增大，左指针i向后移1位也不能保证区间和会减小。

• 思路 ： 同上一题类似

前缀和 + 哈希

class Solution {public static int subarraySum(int[] nums, int k) {int n = nums.length; // 获取数组长度Map<Integer,Integer> map = new HashMap<>(); // 创建哈希表，用于存储前缀和及其出现次数int sum = 0; // 初始化前缀和为0int ans = 0; // 初始化结果为0map.put(sum,1); // 将初始的前缀和0放入哈希表，并设其出现次数为1// 遍历数组for(int num : nums){sum += num; // 计算当前位置的前缀和// 如果哈希表中存在前缀和为sum-k的项，则说明存在和为k的子数组 sum - (sum-k) = kif(map.containsKey(sum - k)){ans += map.get(sum - k); // 更新结果，累加前缀和为sum-k的子数组数量}map.put(sum, map.getOrDefault(sum, 0) + 1); // 更新哈希表，将当前前缀和放入，并更新出现次数}return ans; // 返回结果}
}

• 初始时，将前缀和为 0 放入哈希表 map 中，表示在初始状态下存在一个前缀和为 0 的情况，出现次数为 1。

• 如果 map 中存在 sum - k，则说明从之前的某个位置到当前位置的子数组的和为 k。这是因为 sum - (sum - k) = k。

• 如果存在这样的前缀和，则将该前缀和的出现次数累加到 ans 中。

---

3. LeetCode 523 连续的子数组和

• 这里要用到数学知识——同余定理

1. 前缀和的定义： 设 preSum[i] 表示 nums 数组从 0 到 i 的元素之和。

   • 如果存在一个子数组 nums[j..i] （j < i），其和是 k 的倍数，则 preSum[i] - preSum[j-1] 必须是 k 的倍数。

2. 利用余数的性质(同余定理)：

   • 如果 preSum[i] 和 preSum[j-1] 对 k 取余得到相同的结果，即 (preSum[i] - preSum[j-1]) % k == 0，则存在这样的子数组。
   • a%k = b%k ,则 （a-b）%k =0 满足条件

4. 使用哈希表记录余数： 使用哈希表来记录每个余数第一次出现的位置。

---

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;int[] pre = new int[n + 1];for (int i = 1; i <= n; i++) {pre[i] = pre[i - 1] + nums[i - 1]; // 计算前缀和}Set<Integer> set = new HashSet<>();for (int i = 2; i <= n; i++) {set.add(pre[i - 2] % k); // 将前缀和前两项的同余结果加入集合if (set.contains(pre[i] % k)) return true; // 如果当前前缀和对k取模的结果在集合中已经存在，说明找到了符合条件的子数组}return false; // 如果遍历完没有找到符合条件的子数组，返回false}
}

---

4. LeetCode 724 寻找数组的中心下标

• 前缀和思想

法一：

class Solution {public static int pivotIndex(int[] nums) {int n = nums.length;int[] sumLeft = new int[n]; // 用于存储每个索引位置左侧元素之和int[] sumRight = new int[n]; // 用于存储每个索引位置右侧元素之和sumLeft[0] = 0; // 初始化左侧和数组的第一个元素为0（因为第一个元素左侧没有元素）sumRight[n - 1] = 0; // 初始化右侧和数组的最后一个元素为0（因为最后一个元素右侧没有元素）int sum1 = 0; // 用于计算累积的左侧和int sum2 = 0; // 用于计算累积的右侧和// 计算每个索引位置左侧的累积和for (int i = 0; i < n; i++) {sum1 += nums[i];sumLeft[i] = sum1;}// 计算每个索引位置右侧的累积和for (int i = n - 1; i >= 0; i--) {sum2 += nums[i];sumRight[i] = sum2;}// 遍历数组，找到第一个满足左侧和等于右侧和的索引位置for (int i = 0; i < n; i++) {if (sumLeft[i] == sumRight[i]) {return i;}}// 如果没有找到满足条件的索引，返回-1return -1;}
}

---

法二：

class Solution {public static int pivotIndex(int[] nums) {int totalSum = 0; // 计算整个数组的和for (int num : nums) {totalSum += num;}int leftSum = 0; // 左侧和的初始值为0for (int i = 0; i < nums.length; i++) {int rightSum = totalSum - leftSum - nums[i]; // 右侧和等于总和减去左侧和和当前数字if (leftSum == rightSum) {return i; // 如果左右两侧和相等，则返回当前索引作为轴心索引}leftSum += nums[i]; // 更新左侧和，将当前数字累加到左侧和中}return -1; // 如果遍历完整个数组都没有找到轴心索引，则返回-1表示不存在}
}

---

5. LeetCode 238 除自身以外数组的乘积

• 思路 ：前缀积 + 后缀积 （左右乘积列表）

我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。

注意这里有一个细节就是要除了自己，所以在累乘的时候，要在当前位置保存 左侧 或者 右侧 （不包含自己）。

前积乘后积，先存后乘避开自己

class Solution {public int[] productExceptSelf(int[] nums) {int n= nums.length;// L 和 R 分别表示左右两侧的乘积列表int[] L = new int[n];int[] R = new int[n];int[] answer = new int[n];// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1L[0] = 1;for (int i = 1; i < n; i++) {L[i] = nums[i - 1] * L[i - 1];}// R[i] 为索引 i 右侧所有元素的乘积// 对于索引为 'n-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1R[n- 1] = 1;for (int i = n- 2; i >= 0; i--) {R[i] = nums[i + 1] * R[i + 1];}// 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for (int i = 0; i < n; i++) {answer[i] = L[i] * R[i];}return answer;}
}

---

class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;int[] answer = new int[length];// answer[i] 表示索引 i 左侧所有元素的乘积// 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1answer[0] = 1;for (int i = 1; i < length; i++) {answer[i] = nums[i - 1] * answer[i - 1];}// R 为右侧所有元素的乘积// 刚开始右边没有元素，所以 R = 1int R = 1;for (int i = length - 1; i >= 0; i--) {// 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 Ranswer[i] = answer[i] * R;// R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上R *= nums[i];}return answer;}
}

---

更新于：

本篇blog会持续更新哦~