LeetCode刷题 -- 20200607 前缀和篇（leetcode刷题班）

最近刷题倒是没停，但是感觉大部分遇到的不是很适合拿来水博客，毕竟方法套路比较相似。年兄推荐下做了两道前缀和的题，感觉这类题型的思路很棒，也可以归纳成一个方法，故再来水一篇。题目均来自力扣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表中的数据。

注意对于这道题来说，负数需要特别处理一下。来看看代码吧：

第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。先来看看笔者没有通过的的提交吧:

上面的代码其实已经通过了大多数的测试用例，但在第56个用例失败了。

case 56很简单，输入是[-1,-1,1] ，1。如果按照我的思路，那么储存前缀和的Dict中的结果应该是（-1，2），（-2，1）。即前缀和是-1的情况出现了两次，前缀和是-2的情况出现了一次。此时我们要求的结果K=1, 因此对于前缀和是-2的这种情况，如果我们可以找到前缀和是-1的前缀是不是就满足了呢？我一开始是这么想的，然鹅被现实打脸 (￣ε(#￣) 了。其实题目中满足要求的只有[1] 这种情况。

再仔细思考，其实我遇到的问题是既需要利用Hash来实现O(1)的访问，又需要知道顺序，来过滤到不可能的情况。

再来看看官方的解法吧：

还是想法不够成熟，人家直接放到一次循环里搞定了，边生成Hash集合，边处理数据，同时也避免了上面提到的那种情况。试着解释一下上面那种情况：其实是用已生成的前缀和去减去未生成的前缀和，真实情况下这是不合逻辑的，但是由于先独立的计算了一遍前缀和掩盖了这个问题。

PS: 即使我一开始的思路没错，时间复杂度也是O(2n), 虽然最终可以计算为O(n)。而官方的直接就是O(n)，当数据量不大时，由于常数被官方完爆。ORZ

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。