这道题主要是找规律，优化的时候可以利用哈希表和数组的特性。
原题
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
- 数组的长度为 [1, 20,000]。
- 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
原题url：https://leetcode-cn.com/problems/subarray-sum-equals-k/
解题
一开始的想法肯定就是利用暴力解法了，三层 for 循环的那种，第1层和第2层选择起点和终点，第3层则是计算起点到终点的总和。这样的想法最简单，但很可惜，直接超时了，让我们稍微优化一下。
子数组之和
因为题目要求子数组下标连续，那么我们想想，如果要求sum(i, j)(也就是从下标 i 到下标 j 的子数组之和)，其实可以转化成sum(0, i - 1) - sum(0, j)。这样的话，就可以把上面的三层for循环优化成两层。
接下来我们直接看看代码：
class Solution {
public int subarraySum(int[] nums, int k) {
// sum(i, j) = sum(0, j) - sum(0, i - 1)
int[] sumArray = new int[nums.length];
sumArray[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sumArray[i] = sumArray[i - 1] + nums[i];
}
int result = 0;
int sum = 0;
for (int i = sumArray.length - 1; i >= 0; i--) {
// 前i个数之和
if (sumArray[i] == k) {
result++;
}
// 查询从(j + 1)到i的和
for (int j = i - 1; j >= 0 && j != i; j--) {
sum = sumArray[i] - sumArray[j];
if (sum == k) {
result++;
}
}
}
return result;
}
}
提交OK，但时间复杂度是O(n^2)，优化一下。
用哈希表优化
我们想想，上面使用使用第二层for循环，主要是为了查出 sumArray 中是否还存在等于sumArray[i] - k的数，这明显是一个映射关系，因此我们用一个 map 去记录中间的求和结果。
class Solution {
public int subarraySum(int[] nums, int k) {
// sum(i, j) = sum(0, j) - sum(0, i - 1)
// 用map存储，key为sum，value为第i个数
Map<Integer, List<Integer>> map = new HashMap<>(nums.length * 4 / 3 + 1);
// 数组求和
int sum = 0;
// 记录一共有哪些和
Set<Integer> sumSet = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
sumSet.add(sum);
// 查看当前是否已经记录
List<Integer> indexList = map.get(sum);
if (indexList == null) {
indexList = new LinkedList<>();
}
indexList.add(i);
map.put(sum, indexList);
}
int result = 0;
for (Integer subSum : sumSet) {
List<Integer> list = map.get(subSum);
// 如果list为null，说明是被移除了，说明之前已经计算过
if (list == null) {
continue;
}
if (subSum == k) {
result += map.get(subSum).size();
}
// 剩余的和
int remainSum = subSum - k;
List<Integer> remainList = map.get(remainSum);
// 如果为null，说明不存在
if (remainList == null) {
continue;
}
// 如果不为null，说明存在，则可以进行配对
// 让list和remainList进行配对
for (int index1 : list) {
for (int index2 : remainList) {
if (index1 <= index2) {
continue;
}
result++;
}
}
}
return result;
}
}
提交OK，虽然较之前的方法时间效率上有所提高，但并没有本质区别。特别是最后的双重 for 循环，因为下标只有大的减小的才有意义，这样也就给自己额外增加了运算。
那么反思一下，是否真的有必要提前算好子数组的和？如果一边遍历一边求和，并将求和的结果存入map中，那么 map 中存在的，一定是下标小于自己的求和结果。针对这点，我们可以再做一步优化：
public class Solution {
public int subarraySum(int[] nums, int k) {
// 最终结果的数量
int count = 0;
// 求和
int sum = 0;
// key为中间求出了哪些和，value为当前和有几种情况
HashMap<Integer, Integer> map = new HashMap<>();
// 和为0有1中情况，就是一个数都不选
map.put(0, 1);
// 遍历数组
for (int i = 0; i < nums.length; i++) {
// 求和
sum += nums[i];
// map中是否有记录剩余的值
if (map.containsKey(sum - k)) {
// 累加，此处可以直接添加，是因为求和是从前往后进行的，现在能找到的，说明一定是之前的
count += map.get(sum - k);
}
// 记录当前的值
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
提交OK，这样时间复杂度就变为了O(n)。
数据结构的优化
现在，我们用哈希表来存储中间结果。虽然哈希表的查找效率理论上可以达到O(1)，但考虑到哈希冲突，最坏情况下还是有可能达到O(n)。真正能够保证达到O(1)的数据结构，是数组（用空间换取时间）。
那这个用来存储的一维数组究竟长度该设置为多少呢？自然就是找出数组中子数组之和的最大值和最小值，两者求差，结果就是最终的数组长度。利用这个数组去存储子数组求和的结果，这样就能保证在查找时的效率了。
class Solution {
public int subarraySum(int[] nums, int k) {
int sum = 0;
// sum的最小值和最大值，因为可以一个数值都不选，因此0作为初始值
int min = 0;
int max = 0;
// 求和
for (int n : nums) {
sum += n;
min = Math.min(min, sum);
max = Math.max(max, sum);
}
// sums[i]代表从下标为0到下标为i的子数组之和
// 用一个数组存储，相比于map，取值更快，用空间换取时间
int[] sums = new int[max - min + 1];
// 最终结果
int count = 0;
sum = 0;
// 遍历数组
// 需要重新求和，因为没有类似set这样的结构存储了结果
for (int n : nums) {
// 求和
sum += n;
// 新的目标值
int target = sum - min - k;
// 是否有超过范围
if (target >= 0 && target < sums.length) {
count += sums[target];
}
sums[sum - min]++;
}
// 再加上本身就是k的子数组的数量
if (k - min >= 0 && k - min < sums.length) {
count += sums[k - min];
}
return count;
}
}
提交OK，执行时间上更快了。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要是找规律，优化的时候可以利用哈希表和数组的特性。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
公众号：健程之道
