[LeetCode] 560. Subarray Sum Equals K

ccj659 发布于2019-08-16 13:30 / 2552人阅读

Problem

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution

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

//1, 2, 3, 4, 5, 6          k = 5
//1, 3, 6, 10, 15, 21

//1, 1, 1, 2, 1, 2, 1       k = 3
//1, 2, 3, 5, 6, 8, 9

//1, 2, 0, -1, 0, 1         k = 2
//1, 3, 3,  2, 2, 3

云服务器服务器托管 subarray LeetCode LeetCode_String equals

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71854.html

[LeetCode] Maximum Size Subarray Sum Equals k

Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...

MudOnTire 2019-08-15 15:47 评论0 收藏0
[LeetCode] 523. Continuous Subarray Sum

Problem Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sum...

stackfing 2019-08-16 13:46 评论0 收藏0
[LeetCode] 862. Shortest Subarray with Sum at Leas

摘要：较早放入的元素在队列顶部最近放入的元素在队列尾部检查最近放入的，保证队列中新放入的及对应的均为递增反证若保留，那么在下面第二个循环，该元素有可能中断循环，并使得我们无法得到队列更左边的最优解检查较早放入的最小距离 Problem Return the length of the shortest, non-empty, contiguous subarray of A with sum...

thursday 2019-08-16 13:50 评论0 收藏0
LeetCode 560. 和为 K 的子数组

摘要：当我们以为子数组最后一个元素的时候，不用每次都枚举子数组之间所有元素的和，只需要以为最后一个元素，从后往前累加，即可计算以为最后一个元素的连续子数组。截止到目...

qiangdada 2021-09-22 10:02 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0