LeetCode 560. 和为K的子数组

2020-04-22 00:00:00 数组 leetcode 560.

我的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
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章