苏州做企业网站公司,沈阳思路网站制作,电商网站建设优缺点,网站开发编程语言一、前缀和#xff08;Prefix Sum#xff09;算法概述
前缀和算法通过预先计算数组的累加和#xff0c;可以在常数时间内回答多个区间和相关的查询问题#xff0c;是解决子数组和问题中的重要工具。 它的基本思想是通过预先计算和存储数组的前缀和#xff0c;可以在 O(1)…一、前缀和Prefix Sum算法概述
前缀和算法通过预先计算数组的累加和可以在常数时间内回答多个区间和相关的查询问题是解决子数组和问题中的重要工具。 它的基本思想是通过预先计算和存储数组的前缀和可以在 O(1) 的时间复杂度内计算任意子数组的和。 定义 对于数组 nums其前缀和 prefix[i] 定义为从数组起始位置到第 i 个元素的累加和。 具体公式prefix[i] nums[0] nums[1] ... nums[i]。
计算方法 首先创建一个额外的数组或哈希表用来存储每个位置的前缀和。通过一次遍历数组依次计算并填充这个数组或哈希表。 应用 快速计算子数组和通过前缀和可以快速计算任意子数组的和。例如子数组 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; // 数组的长度MapInteger,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; // 获取数组长度MapInteger,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 连续的子数组和 这里要用到数学知识——同余定理 前缀和的定义 设 preSum[i] 表示 nums 数组从 0 到 i 的元素之和。 如果存在一个子数组 nums[j..i] j i其和是 k 的倍数则 preSum[i] - preSum[j-1] 必须是 k 的倍数。 利用余数的性质(同余定理) 如果 preSum[i] 和 preSum[j-1] 对 k 取余得到相同的结果即 (preSum[i] - preSum[j-1]) % k 0则存在这样的子数组。a%k b%k ,则 a-b%k 0 满足条件 使用哈希表记录余数 使用哈希表来记录每个余数第一次出现的位置。 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]; // 计算前缀和}SetInteger 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会持续更新哦~
