Interview 150
Subarray Sum Equals K
- Problem
- LC 560
- File
- interview150_LC560SubarraySumEqualsK.java
- Path
- pkg5leetcode/interview150/interview150_LC560SubarraySumEqualsK.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC560SubarraySumEqualsK.java
- Lesson
- Back to the chapter
- Approach
- Prefix sum hash map counts subarrays with needed prefix.
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Subarray Sum Equals K | LC 5605 * APPROACH: Prefix sum hash map counts subarrays with needed prefix.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class interview150_LC560SubarraySumEqualsK {11 static int subarraySum(int[] nums, int k) {12 Map<Integer, Integer> cnt = new HashMap<>();13 cnt.put(0, 1);14 int sum = 0, res = 0;15 for (int x : nums) {16 sum += x;17 res += cnt.getOrDefault(sum - k, 0);18 cnt.merge(sum, 1, Integer::sum);19 }20 return res;21 }22 23 public static void main(String[] args) {24 check(subarraySum(new int[]{1, 1, 1}, 2) == 2, "case1");25 check(subarraySum(new int[]{1, 2, 3}, 3) == 2, "case2");26 System.out.println("all tests passed");27 }28 29 static void check(boolean cond, String name) {30 if (!cond) throw new AssertionError("FAILED: " + name);31 System.out.println(" PASS " + name);32 }33}