It hurts to remember，but it would be worse to forget.

铭记虽痛苦，但遗忘更糟糕。

问题描述

来源：LeetCode第560题

难度：中等

给定一个整数数组和一个整数k，你需要找到该数组中和为k的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2

输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

数组的长度为[1,20,000]。

数组中元素的范围是[-1000,1000]，且整数k的范围是[-1e7, 1e7]。

暴力求解

暴力求解是最容易想到的，枚举数组nuns的所有子数组，然后统计所有子数组和等于k的个数

来看下代码


时间复杂度：O(n^3)。

空间复杂度：O(1)。

这种时间复杂度太高，当数据量比较大的时候，很容易超时，我们再来优化一下。当我们以nums[j]为子数组最后一个元素的时候，不用每次都枚举子数组[i……j]之间所有元素的和，只需要以nums[j]为最后一个元素，从后往前累加，即可计算以nums[j]为最后一个元素的连续子数组。比较绕，来看个图

来看下代码

时间复杂度：O(n^2)。

空间复杂度：O(1)。

时间复杂度从n^3降到了n^2，我们再来看一个时间复杂度为n的解决方式，就是前缀和。

前缀和解决

所谓前缀和就是数组中前面n个元素的和，比如前缀和pre[i]的值是：

pre[i]=nums[0]+nums[1]+……+nums[i];

前缀和pre[j]的值是：

pre[j]=nums[0]+nums[1]+……+nums[i]+nums[i+1]+……+nums[j];

如果我们要求子数组[i……j]之间所有元素的和，也就是

nums[i]+nums[i+1]+……+nums[j]=pre[j]-pre[i-1]；

也就是说如果pre[j]-pre[i-1]等于k，说明我们找到了一个和为k个连续子数组，这就变成了两数之和问题。因为k的值是固定的，如果枚举pre[j]，我们只需要统计pre[i-1]的个数即可，这个统计方式可以使用map来解决，看下代码（这里为了方便计算，pre长度增加1，pre[0]=0）

时间复杂度：O(n)。
空间复杂度：O(n)。


本文原创，未经作者允许不可转载！
更多内容，欢迎关注作者微信公众号：数据结构和算法！