438. 找到字符串中所有字母异位词Medium( 三 ) _数组

560. 和为 K 的子数组
暴力解法，两层循环，i为子数组结尾，j为子数组开头，判断他们之间的和是不是等于k 。会超时。
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)for i in range(n):sum = 0for j in range(i, -1, -1):sum += nums[j]if sum == k:count += 1return count
暴力解法
这一题是要找到所有连续子数组的和等于k的个数。那么怎么求一个数组的连续子数组呢。可以使用两层循环来实现。
n = len(nums)subnums = []for i in range(n):for j in range(i, n):subnums.append(nums[i:j+1])
既然这样，稍作修改，就可以求连续子数组和为k的个数了。
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)for i in range(n):for j in range(i, n):if sum(nums[i:j+1]) == k:count += 1return count
很明显，这么做的时间复杂度是 O ( n 3 ) O(n^3) O(n3) 。因为除了两层for循环，还有一层求和。
其实，可以对上面方法做一些优化。因为我们求 n u m s [ i : j + 1 ] nums[i:j+1] nums[i:j+1]的下一次 n u m s [ i : j + 1 + 1 ] nums[i:j+1+1] nums[i:j+1+1]，其实只比前一次多了一个 n u m s [ j + 1 ] nums[j+1] nums[j+1] 。那么我们就没必要每次都从i开始算了。
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)for i in range(n):sum = 0for j in range(i, n):sum += nums[j]if sum == k:count += 1return count
这一下，时间复杂度降到了 O ( n 2 ) O(n^2) O(n2) 。
但是很可惜，这样依然会超时。
前缀和
什么是前缀和：前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）
通常，会在前缀和首位放一个0 。比如数组 [ 1 , 2 , 3 ] [1,2,3] [1,2,3] 。其前缀和是 [ 0 , 1 , 2 , 6 ] [0,1,2,6] [0,1,2,6]
前缀和通常可以帮助我们快速计算某个区间内的和。比如我们要算 i , j i,j i,j之间的和，那么就是 n u m s [ i ] + n u m s [ i + 1 ] + ? + n u m s [ j ] nums[i] + nums[i+1] + \cdots +nums[j] nums[i]+nums[i+1]+?+nums[j] 。他可以看作是 n u m s [ 0 ] + n u m s [ 1 ] + ? + n u m s [ i ] + n u m s [ i + 1 ] + ? + n u m s [ j ] nums[0] + nums[1] + \cdots + nums[i] + nums[i+1] + \cdots +nums[j] nums[0]+nums[1]+?+nums[i]+nums[i+1]+?+nums[j]减去 n u m s [ 0 ] + n u m s [ 1 ] + ? + n u m s [ i ? 1 ] nums[0] + nums[1] + \cdots + nums[i-1] nums[0]+nums[1]+?+nums[i?1] 。这个式子也是 p r e S u m [ j ] ? p r e S u m [ i ? 1 ] [j] - [i-1] [j]?[i?1] 。
那么，我们先遍历一次数组，求出前缀和数组。之后这个数组可以代替我们最开始暴力解法的 s u m sum sum函数。但是很遗憾，这种做法复杂度还是 O ( n 2 ) O(n^2) O(n2)
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)preSum = [0]# 求前缀和数组tmp = 0for i in range(n):tmp += nums[i]preSum.append(tmp)# 求和为k的连续子数组，求i到j之间的和for i in range(1, n+1):for j in range(i, n+1):if preSum[j] - preSum[i-1] == k:# preSum[j] - preSum[i-1]代表着在nums数组中，前j个数之和减去前i-1个数之和count += 1return count
进一步优化的话，我们可以边算前缀和，边统计。遍历过程中，我们统计历史中每一个前缀和出现的个数，然后计算到 i i i位置（含 i i i）的前缀和 p r e s u m减去目标 k k k在历史上出现过几次，假如出现过 m m m次，代表第 i i i位以前（不含 i i i）有 m m m个连续子数组的和为 p r e s u m ? k- k ?k，这 m m m个和为 p r e s u m ? k- k ?k的连续子数组，每一个都可以和 p r e s u m组合成为 p r e s u m ? ( p r e s u m ? k ) = k- ( - k) = k ?(?k)=k 。