qidao123.com技术社区-IT企服评测·应用市场

标题: 前缀和 [打印本页]

---

作者: 泉缘泉    时间: 2025-3-30 20:31
标题: 前缀和
前缀和

前缀和又称累计和，是指将序列中从起始位置到当前位置的全部元素进行求和

1. prefixSum[0] = nums[0]
2. prefixSum[1] = nums[0] + nums[1]
3. prefixSum[2] = nums[0] + nums[1] + nums[2]
4. ...
5. prefixSum[i] = nums[0] + nums[1] + ... + nums[i]

复制代码

解题操作顺序

• 先求前缀和pre
  
• 判断当前pre-k是否在hashmap中并完成计数
  
• 最后将pre加入hashmap
  

560. 和为 K 的子数组

留意初始添加mp.put(0, 1)，记录前缀和为0的次数为1
关键变量解析（pre,mp,count，均为全局变量）

1. pre（前缀和）

• 含义：从数组起始位置到当前位置 i 的全部元素之和，即 pre = nums[0] + nums[1] + ... + nums。
  
• 作用：将子数组和问题转化为前缀和的差值问题。比方，子数组 nums[j..i] 的和为 pre - pre[j]。
  

2. mp（哈希表）

• 含义：键为前缀和的值，值为该前缀和出现的次数。
  
• 作用：快速查询历史前缀和的出现次数，判断是否存在满意条件的子数组。
  

3. count（计数器）

• 含义：记录满意和为 k 的子数组的总数量。
  
• 作用：累加全部大概的子数组组合。
  

官方题解：

1. public class Solution {
2.     public int subarraySum(int[] nums, int k) {
3.         int count = 0, pre = 0;
4.         HashMap < Integer, Integer > mp = new HashMap < > ();
5.         mp.put(0, 1);
6.         for (int i = 0; i < nums.length; i++) {
7.             pre += nums[i];
8.             if (mp.containsKey(pre - k)) {
9.                 count += mp.get(pre - k);
10.             }
11.             mp.put(pre, mp.getOrDefault(pre, 0) + 1);
12.         }
13.         return count;
14.     }
15. }

复制代码

我的第一次实现：
也不能用双指针，因为数据中大概包罗负数。
[code]public int subarraySum(int[] nums, int k) {    int res = 0;    int[] preSum = new int[nums.length+1];    preSum[0] = 0;    for(int i=1;i

---

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.4