算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试 算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 和为 K 的子数组，我们先来看题面：
https://leetcode-cn.com/problems/subarray-sum-equals-k/
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例
代码语言：javascript复制示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2解题
Map 实现（时间复杂度 O(N)）
1、建立 map 表用于存储每个连续子数组 sum 求和出现的次数，初始化为（0,1），表示和为 0 的连续子数组出现 1 次；
2、sum 的值是在对 nums 数组的循环中不断累加当前元素的，res 的值则需要查找 map 中是否已存在和为 sum - k 的连续数组，也就是在查找此前所有从 0 项开始累加的连续子项和中有没有 sum - k。
3、如果有的话，则说明从该项到当前项的连续子数组和必定为 k，那么 res 则可以和这个 sum 的对应值，即这个 sum 出现的次数，相加得到新的 res。
4、对于当前 sum 如果已存在与 map 中则其对应值 1，不存在则添加新项，初始值为 1。
代码语言：javascript复制class Solution {
public int subarraySum(int[] nums, int k) {
int sum = 0;
int res = 0;
Map<Integer, Integer> preSum = new HashMap<>();
preSum.put(0, 1);
for(int i = 0; i < nums.length; i ){
sum = nums[i];
// 判断是否存在和为sum - k的连续式数组，如果存在，那么一定存在和为k的连续数组
// 每次都是从数组起始位置累加的
if(preSum.containsKey(sum - k)){
res = preSum.get(sum - k);
}
// 如果不存在sum-k的连续子数组，则将sum的连续子数组存进preSum里
preSum.put(sum, preSum.getOrDefault(sum, 0) 1);
}
return res;
}
}好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
上期推文：
LeetCode1-540题汇总，希望对你有点帮助！
LeetCode刷题实战541：反转字符串 II
LeetCode刷题实战542：01 矩阵
LeetCode刷题实战543：二叉树的直径
LeetCode刷题实战544：输出比赛匹配对
LeetCode刷题实战545：二叉树的边界
LeetCode刷题实战546：移除盒子
LeetCode刷题实战547：省份数量
LeetCode刷题实战548：将数组分割成和相等的子数组
LeetCode刷题实战549：二叉树中最长的连续序列
LeetCode刷题实战550：游戏玩法分析 IV
LeetCode刷题实战551：学生出勤记录 I
LeetCode刷题实战552：学生出勤记录 II
LeetCode刷题实战553：最优除法
LeetCode刷题实战554：砖墙
LeetCode刷题实战555：分割连接字符串
LeetCode刷题实战556：下一个更大元素 III
LeetCode刷题实战557：反转字符串中的单词 III
LeetCode刷题实战558：四叉树交集
LeetCode刷题实战559：N 叉树的最大深度
