LeetCode 560. 和为K的子数组

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 560. 和为K的子数组

题目

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

示例 1 :

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

说明 :

• 数组的长度为 [1, 20,000]。
• 数组中元素的范围是 [-1000, 1000] ，且整数?k?的范围是?[-1e7, 1e7]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

本题与LeetCode 1248. 统计「优美子数组」为同类问题，可对比学习；

思路1-用map记录累加和；

思路解析：如果i和j之间的和为k，i之前的和为sum1，j之前的和为sum2，那么就有sum2-sum1=k，所以使用map一次遍历并记录以sum为key，value为其出现的次数；
需要注意的是，起始map需要添加(0,1)对，代表sum-k为0时出现了1次，举个例子，若k=10，数组第一项就是10，那么sum-k=0，但0此时不在map，就少了一次count;

1. 建map，初始add(0,1)，新建统计变量count=0;
2. 遍历累加sum，且看map中是否有sum-k，有则累加至count；
3. 以sum为key，更新map；

算法复杂度:

• 时间复杂度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(n\right)}} $

算法源码示例

package leetcode;

import java.util.HashMap;

/**
 * @author ZhouJie
 * @date 2020年4月21日 下午8:47:12 
 * @Description: 560. 和为K的子数组
 *
 */
public class LeetCode_0560 {

}

class Solution_0560 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年4月21日 下午8:47:49 
	 * @param: @param nums
	 * @param: @param k
	 * @param: @return
	 * @return: int
	 * @Description: 1-map存储前缀和；
	 *
	 */
	public int subarraySum_(int[] nums, int k) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		// 初始必须存入(0,1)，若不存而数组的第一项就是k，sum-k=0时就找不到0了
		map.put(0, 1);
		int sum = 0, count = 0;
		for (int val : nums) {
			sum += val;
			int key = sum - k;
			// 寻找之前是不是存过sum-k，有就表示找到了一个和为k的片段
			if (map.containsKey(key)) {
				count += map.get(key);
			}
			// 更新和为sum的出现次数
			map.put(sum, map.getOrDefault(sum, 0) + 1);
		}
		return count;
	}
}

原文链接:https://www.cnblogs.com/izhoujie/p/12747826.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有