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

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

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

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

Eva W.

2021-01-05

2021-01-31