1. 代码段小站首页
  2. 算法

leetcode560-和为K的子数组

彭晨涛 • • 算法 • 阅读 41

原题

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

示例 1:

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

说明 :

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

解法

思想

连续的数组之和其实可以转换为两个前缀和的差值。使用一个哈希表存储截至每一个元素的前缀和以及该值的出现次数，后面任一时刻的前缀和减去k如果在哈希表中存在，就加上它的出现次数。

代码

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (map.containsKey(pre - k))
                count += map.get(pre - k);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode560-%e5%92%8c%e4%b8%bak%e7%9a%84%e5%ad%90%e6%95%b0%e7%bb%84/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年5月14日 22:40
下一篇 2020年5月15日 22:01

相关推荐

  • leetcode102-二叉树的层次遍历

    原题 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如:给定二叉树: [3,9,20,null,null,15,7],  &nbsp...

    彭晨涛 彭晨涛
    算法 2020年1月11日
    070

  • 程序员面试金典08.01-三步问题

    原题（来源Leetcode） 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模...

    彭晨涛 彭晨涛
    算法 2020年6月19日
    03520

  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。 给定石子的位置列表（用单...

    彭晨涛 彭晨涛
    算法 2020年6月16日
    03040

  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格...

    彭晨涛 彭晨涛
    算法 2020年4月12日
    0100

  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, b...

    彭晨涛 彭晨涛
    算法 2019年11月18日
    060
  • leetcode138-复制带随机指针的链表 算法

    leetcode138-复制带随机指针的链表

    这道题和leetcode133-克隆图有异曲同工之妙。 原题 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。...

    彭晨涛 彭晨涛
    2019年12月17日
    0280

  • 用一个栈实现另一个栈的排序

    原题（来源牛客网） 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？ 解法 ...

    彭晨涛 彭晨涛
    算法 2020年4月20日
    01010

  • leetcode367-有效的完全平方数

    原题 给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。 说明： 不要使用任何内置的库函数，如  sqrt。 示例1： ...

    彭晨涛 彭晨涛
    算法 2020年1月5日
    0110

  • leetcode914-卡牌分组

    原题 给定一副牌，每张牌上都写着一个整数。 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组： 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。...

    彭晨涛 彭晨涛
    算法 2020年3月27日
    080

  • leetcode49-字母异位词分组

    原题 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 示例： 输入： ["eat", "tea", "tan", "ate", "nat",...

    彭晨涛 彭晨涛
    算法 2019年12月25日
    090

发表回复

登录后才能评论