Subarray Sum Equals K

Subarray Sum Equals K is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Frequency Map / Counting subpattern.

Problem statement

Given an integer array nums and an integer k, consider every non-empty subarray of nums. A subarray is a contiguous sequence of one or more elements, and its sum is the total of its elements.

Return the number of distinct contiguous ranges whose elements add up to exactly k. Count each range separately, even when different ranges contain the same values.

Example 1:

Input: nums = [2,-1,2], k = 3 Output: 1 Explanation: Only the entire array has sum 3.

Example 2:

Input: nums = [4,-3,5,-2,1], k = 2 Output: 1 Explanation: The only qualifying subarray is [-3, 5], which sums to 2.

Example 3:

Input: nums = [0,0,0], k = 0 Output: 6 Explanation: Every non-empty contiguous range has sum 0, giving 3 single-element, 2 two-element, and 1 three-element subarray.

Constraints:

- 1 <= nums.length <= 2 10^4 - -1000 <= nums[i] <= 1000 - -10^7 <= k <= 10^7 - nums contains integers - k is an integer

Topics and companies

Topics: Array, Hash Table, Prefix Sum, Counting.

How to practise Subarray Sum Equals K on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) average time time and O(n) space.

Open Subarray Sum Equals K in the code editor, or read the Subarray Sum Equals K editorial for a worked solution with its approach and complexity analysis.

Where Subarray Sum Equals K sits in the DSA pattern sheet

Problems related to Subarray Sum Equals K

Other problems that use the same Hashing - Frequency Map / Counting and Array/Matrix Manipulation Patterns techniques:

Preparing this workspace.