> LeetCode560. 和为K的子数组 - Yuyy
Yuyy
Yuyy
LeetCode560. 和为K的子数组

思路

首先想到的是暴力求解,双重循环得出所有连续子串,但是多半要超时。没想到其他办法。看了题解,学到了前缀和的概念,这里的子串和等于end的前缀和减去start的前缀和。在前缀和的基础上,结合了hash来优化,也就是两数之和那道题。

两个地方需要注意。一、需要的前缀和可能出现多次,那么每次都得算上。二、前缀和为0也是一种情况,并且是必要的,需要手动添加。例如目标为0。

题目

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

示例 1 :

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

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ,且整数 的范围是 [-1e7, 1e7]。
Related Topics
  • 数组
  • 哈希表
  • 前缀和
  • 👍 1078
  • 👎 0
  • 代码

            public int subarraySum(int[] nums, int k) {
    
                // key前缀和,value出现的次数
                Map<Integer, Integer> qzh = new HashMap<>(nums.length);
                // 子串长度为0(在母串最前面),前缀和为0,出现次数+1(原本为0)
                qzh.put(0, 1);
                // 前缀和
                int sum = 0;
                int res = 0;
    
                for (int num : nums) {
                    sum += num;
                    // 找出需要的前缀和
                    final Integer target = qzh.get(sum - k);
                    if (target != null) {
                        res += target;
                    }
                    // 保存当前前缀和出现的次数
                    qzh.put(sum, qzh.getOrDefault(sum, 0) + 1);
                }
                return res;
            }
    

    发表评论

    textsms
    account_circle
    email

    • http://1.gravatar.com/avatar/7802fb41e0c9c7690a87c46d99e34da4?s=80&d=monsterid&r=g
      admin博主

      又开始刷题了,一边复习一边刷

      2月前回复

    Yuyy

    LeetCode560. 和为K的子数组
    思路 首先想到的是暴力求解,双重循环得出所有连续子串,但是多半要超时。没想到其他办法。看了题解,学到了前缀和的概念,这里的子串和等于end的前缀和减去start的前缀和。在前缀和的基…
    扫描二维码继续阅读
    2021-09-02
    友情链接
    标签
    归档
    近期文章
    分类
    近期文章