560. Subarray Sum Equals K

Medium

Array

Hash Table

Prefix Sum

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

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

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.

Acceptance

46.5%

Submissions

4,706,743

Accepted

2,189,587