1.算法题目
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
2.算法思路
- 暴力法：考虑给定数组 sums 的每个可能的子数组，找到每个子数组的总和，并检查总和是否等于 k，等于时递增用于记录所需结果的 count；时间复杂度为 O(n^3)，空间复杂度为 O(1)，超出时间限制；
- 使用累计和：计算数组的每个数字开始到累加后面每个数字的和，遇到和为 k时， count 加1；需要两层循环遍历，时间复杂度为 O(n^2)，空间复杂度为 O(1)；
- 使用哈希表：使用一个哈希表 map ，它用于存储所有可能的索引的累积总和以及相同累加和发生的次数，遍历数组 nums 并继续寻找累积总和。每当我们遇到一个新的和时，我们在hashmap中创建一个与该总和相对应的新条目。如果再次出现相同的和，我们增加与 map 中的和相对应的计数；对于遇到的每个总和，确定已经发生 sum-k 总和的次数，因为它将确定具有总和 k 的子阵列到当前索引的次数，同时将 count 增加相同的数量。最后得到的 count 即为满足题意的值。只需要一次循环遍历数组，但需要 map的辅助空间，时间复杂度为 O(n)，空间复杂度为 O(n)；
3.算法代码
根据累计和算法思路，编写的算法代码如下：
public static int subarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int count = 0;
for (int i = 0; i < nums.length; i ++) {
int sum = 0;
for (int j = i; j < nums.length; j ++) {
sum += nums[j];
if (sum == k) {
count ++;
}
}
}
return count;
}
根据哈希表算法思路，编写的算法代码如下：
public int subarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
HashMap<Integer, Integer> map = new HashMap<>();
int count = 0, sum = 0;
map.put(0, 1);
for (int i = 0; i < nums.length; i ++) {
sum += nums[i];
if (map.containsKey(sum - k)) { // 和为 sum - k 的数据与和为 sum 的区间数的和即为 k，这个区间的数即为满足题意的和为 k 的连续的子数组的数
count += map.get(sum - k);
}
// 保存和为 sum 的数量
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
如果你有疑问或更好的算法思路，欢迎留言交流！！！
如果感觉我的文章对您有所帮助，麻烦动动小手给个喜欢，谢谢！！！
