-
C#教程之LeetCode刷题 -- 20200607 前缀和篇
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/
最近刷题倒是没停，但是感觉大部分遇到的不是很适合拿来水博客，毕竟方法套路比较相似。年兄推荐下做了两道前缀和的题，感觉这类题型的思路很棒，也可以归纳成一个方法，故再来水一篇。题目均来自力扣Leetcode，传送门。
简单来说，前缀和适合于解决 连续，求和 相关的问题。遇到的问题如果包含相关要求，可以考虑尝试一下前缀和的解法。诸如子数组的哈，连续几个数字的和，等等。
974. 和可被 K 整除的子数组
示例：
输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
提示：
1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000
如题目描述，根据给定的数组我们需要寻找到它的子数组满足条件 ==》子数组所有数字的和可以被K整除。注意这里有个隐含条件，子数组的每一项的索引是连续的。
假设一组数组每一项的值都和它的下标相同:
-
- Sumx = 1 + 2 + 3 + ... + x
- Sumy = 1 + 2 + 3 + ... + y
这里不妨假设y>x, 那么 Sumy - Sumx = (x+1) + (x+2) + ... y 。这里Sumy - Sumx 就是数组从x到y的和，我们要寻找的就是 (Sumy - Sumx ) % K = 0的子数组。因此可以转化为Sumy % K == Sumx % K的前缀和表达。而前缀和其实我们是可以通过一次遍历就获得的，只需要一个变量辅助记录上一个位置的前缀和即可。
现在我们的题目转化为了求得Sumy % K == Sumx % K的子数组的个数，并且也知道了怎么计算前缀和。现在只需要使用Hash表来记录前缀和出现的次数即可。当hash表中出现了Key相同的元素，说明我们遇到了前缀和相同，即符合条件的子数组。注意这里同时也要更新一下Hash表中的数据。
注意对于这道题来说，负数需要特别处理一下。来看看代码吧：
1 public class Solution { 2 public int SubarraysDivByK(int[] A, int K) 3 { 4 int result = 0; 5 List<int> preSum = new List<int>(); 6 preSum.Add(0); 7 8 Dictionary<int, int> dict = new Dictionary<int, int>(); 9 dict.Add(0, 1); 10 11 for (int i = 0; i < A.Length; i++) 12 { 13 preSum.Add(preSum[i] + A[i]); 14 int temp = preSum[i + 1] % K; 15 temp = temp < 0 ? temp + K : temp; 16 17 if (dict.Keys.Contains(temp)) 18 { 19 result += dict[temp]; 20 dict[temp] = dict[temp] + 1; 21 } 22 else 23 { 24 dict.Add(temp, 1); 25 } 26 27 } 28 29 return result; 30 } 31 }
第15行，处理一下负数的情况，将其转为对应的%操作取得的正整数。
560. 和为K的子数组
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
这道题目的思路也是一样，但我还是把它记录了下来，因为觉得对比自己的思路和官方思路的过程很有意思。 解法和前面类似，我们也需要利用前缀和来求解。只不过这类是Sumy - Sumx = K。先来看看笔者没有通过的的提交吧:
1 public class Solution { 2 public int SubarraySum(int[] nums, int k) 3 { 4 Dictionary<int, int> dict = new Dictionary<int, int>(); 5 6 int sum = 0; 7 8 for (int i = 0; i < nums.Length; i++) 9 { 10 sum += nums[i]; 11 int count = 0; 12 dict.TryGetValue(sum, out count); 13 dict[sum] = ++count; 14 } 15 16 int result = 0; 17 18 foreach (var item in dict) 19 { 20 if (item.Key == k) 21 { 22 result += item.Value; 23 } 24 25 int temp = item.Key + k; 26 27 if (dict.Keys.Contains(temp)) 28 { 29 if (temp != item.Key) 30 { 31 result += item.Value * dict[temp]; 32 } 33 else 34 { 35 result += (dict[temp] - 1) * (dict[temp] - 1); 36 } 37 38 } 39 40 } 41 42 return result; 43 } 44 }
上面的代码其实已经通过了大多数的测试用例，但在第56个用例失败了。
case 56很简单，输入是[-1,-1,1] ，1。如果按照我的思路，那么储存前缀和的Dict中的结果应该是（-1，2），（-2，1）。即前缀和是-1的情况出现了两次，前缀和是-2的情况出现了一次。此时我们要求的结果K=1, 因此对于前缀和是-2的这种情况，如果我们可以找到前缀和是-1的前缀是不是就满足了呢？我一开始是这么想的，然鹅被现实打脸 (￣ε(#￣) 了。其实题目中满足要求的只有[1] 这种情况。
再仔细思考，其实我遇到的问题是既需要利用Hash来实现O(1)的访问，又需要知道顺序，来过滤到不可能的情况。
再来看看官方的解法吧：
1 public class Solution { 2 public int SubarraySum(int[] nums, int k) 3 { 4 Dictionary<int, int> dict = new Dictionary<int, int>(); 5 6 int sum = 0; 7 int result = 0; 8 9 for (int i = 0; i < nums.Length; i++) 10 { 11 sum += nums[i]; 12 13 int cha = sum - k; 14 15 if (cha == 0) 16 result++; 17 18 if (dict.Keys.Contains(cha)) 19 result += dict[cha]; 20 21 int count = 0; 22 dict.TryGetValue(sum, out count); 23 dict[sum] = ++count; 24 } 25 26 return result; 27 } 28 }
还是想法不够成熟，人家直接放到一次循环里搞定了，边生成Hash集合，边处理数据，同时也避免了上面提到的那种情况。试着解释一下上面那种情况：其实是用已生成的前缀和去减去未生成的前缀和，真实情况下这是不合逻辑的，但是由于先独立的计算了一遍前缀和掩盖了这个问题。
PS: 即使我一开始的思路没错，时间复杂度也是O(2n), 虽然最终可以计算为O(n)。而官方的直接就是O(n)，当数据量不大时，由于常数被官方完爆。ORZ
