[LeetCode] 560. Subarray Sum Equals K

ccj659 發布于2019-08-16 13:30 / 2669人閱讀

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

云服務器 GPU云服務器 subarray LeetCode LeetCode_String equals

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0