subarray_sum_equals_k

README

< Previous 　　　　　　　　　　　　　　　　 Next >

560. Subarray Sum Equals K (Medium)

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].

Related Topics

[Array] [Hash Table]

Similar Questions

1. Two Sum (Easy)
2. Continuous Subarray Sum (Medium)
3. Subarray Product Less Than K (Medium)
4. Find Pivot Index (Easy)
5. Subarray Sums Divisible by K (Medium)

Hints

Hint 1

Will Brute force work here? Try to optimize it.

Hint 2

Can we optimize it by using some extra space?

Hint 3

What about storing sum frequencies in a hash table? Will it be useful?

Hint 4

sum(i,j)=sum(0,j)-sum(0,i), where sum(i,j) represents the sum of all the elements from index i to j-1.

Can we use this property to optimize it.