Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Subarray Sum Equals K

Posted on March 14, 2018July 26, 2020 by braindenny

Subarray Sum Equals K



Similar Problems:

  • LeetCode: Number of Submatrices That Sum to Target
  • Minimum Size Subarray Sum
  • Binary Subarrays With Sum
  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #hashmap, #subarray, #presum

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:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/subarray-sum-equals-k
## Basic Ideas: presum + hashmap
##
## Complexity: Time O(n), Space O(n)
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # value -> count
        freqs = collections.defaultdict(int)
        freqs[0] = 1
        n = len(nums)
        res, presum = 0, 0
        for i in range(n):
            presum += nums[i]
            res += freqs[presum-k]
            freqs[presum] += 1
        return res
// https://code.dennyzhang.com/subarray-sum-equals-k
// Basic Ideas: Presum + Dynamic Programming
//     Count how many subarray ends with current item
// Complexity: Time O(n), Space (n)
func subarraySum(nums []int, k int) int {
    res, preSum := 0, 0
    h := map[int]int{0: 1}
    for _, v := range nums {
       preSum += v
       res += h[preSum - k]
       h[preSum]++
    }
    return res
}
linkedin
github
slack

Post Views: 8
Posted in BasicTagged #subarray, hashmap, presum

Post navigation

LeetCode: Subarray Product Less Than K
LeetCode: Continuous Subarray Sum

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.