Hash Table, Sum

Hash Table, Sum

key word: hastable, prefix sum, running sum
leetcode: 560, 1, 523, 713, 724, 974, 1658
mark: 713

560. Subarray Sum Equals K

Question:
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Examples:

  • Input: nums = [1,1,1], k = 2 ; Output: 2
  • Input: nums = [1,2,3], k = 3 ; Output: 2
  • Input: nums = [1,2,-1,1,3], k = 3 ; Output: 4

Algo: cumulative sum, hashmap

  1. cumulative sum: cum_sum[l.idx : r.idx] = cum_sum[0: r.idx] - cum_sum[0: l.idx]
  2. hashmap: record all possible situations {sum: cnts} till i.idx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 560. Subarray Sum Equals K
from collections import defaultdict

# Time O(n) | Space O(n)
def subarraySum(nums, k):
"""
type nums: List[int]
type k: int
rtype: int
"""
count, cum_sum = 0, 0
running_sum = defaultdict(int)
running_sum[0] = 1

for n in nums:
cum_sum += n
# cum_sum - pre.cum_sum = k,
# cur_sum slice sum - pre.cur_sum slice sum = k
count += running_sum[cum_sum - k]
running_sum[cum_sum] += 1

return count

Similar Questions:

1. Two Sum

Question:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Example:

  • Input: nums = [2,7,11,15], target = 9
  • Output: [0,1]
  • Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Algo: potential num, hashtable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 1. Two Sum
# one-pass hastable: time O(n), space O(n)
def twoSum(nums, target):
"""
type nums: List[int]
type target: int
rtype: List[int], return indices of two nums
"""
buff = {}
for i, num in enumerate(nums):
if num in buff:
return [buff[num], i]
else:
potential = target - num
buff[potential] = i
return []

523. Continuous Subarray Sum

Question:

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 a multiple of k, that is, sums up to n*k where n is also an integer.

Algo: mod of prefix sum, diff of indices larger than 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def checkSubarraySum(nums, k):
"""
type nums: List[int]
type k: int
rtype: bool
"""
# prefix_mod {rem: idx}
prefix_mod = defaultdict(int)
prefix_mod[0] = -1
rem = 0

for i, num in enumerate(nums):
rem += num
if k != 0:
rem = rem % k
if rem in prefix_mod:
if i - prefix_mod[rem] > 1:
return True
else:
prefix_mod[rem] = i

return false

713. Subarray Product Less Than K

Question:

Given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Algo: prefix products, hashmap

1
2
3
4
5
6
7
8
9

def numSubarrayProductLessThanK(nums, k):
if k <= 1: return 0 # all positive integers nums
prefix_prod = defaultdict(int)
prod = 1
for i, num in enumerate(nums):
prod = prod * num
while prod >= k:

724. Find Pivot Index

974. Subarray Sums Divisible by K

1658. Minimum Operations to Reduce X to Zero

Author

Eva W.

Posted on

2021-01-05

Updated on

2021-01-06

Licensed under

Comments