leetcode 560. Subarray Sum Equals K

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:

The length of the array is in range [1, 20,000].The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

这道题还算简单。如果用 DP[i][j] 来做（i是子串的开始index，j是子串的结束index，DP[i][j] 存储 i ~ j 的和），会 Memory Limit Exceed.

需要注意的测试用例有两个。

1.

2.  [ -1, 1, 0, -1, 1]

这道题用最简单的方法就可以AC。

public int subarraySum(int[] nums, int k) { int count=0; for(int begin=0;begin<nums.length;begin++){ int sum=0; for(int end=begin;end<nums.length;end++){ sum+=nums[end]; if(sum==k){ count++; } } } return count; }这道题有solutions： https://leetcode.com/problems/subarray-sum-equals-k/solution/

Approach #2 Using Cummulative sum [Accepted]

Algorithm

我们定义了一个累积数组$sum[]$, 其中$sum[i]$ 存储了 0 ~ (i−1)​th​​ index 的和。要想得到 SUM[i, j]，只需要知道 SUM[0, i - 1] 和 SUM[0, j] 就好了。SUM$[i~j]$= $sum[j]-sum[i-1]$.

Java

public class Solution { public int subarraySum(int[] nums, int k) { int count = 0; int[] sum = new int[nums.length + 1]; sum[0] = 0; for (int i = 1; i <= nums.length; i++) sum[i] = sum[i - 1] + nums[i - 1]; for (int start = 0; start < nums.length; start++) { for (int end = start + 1; end <= nums.length; end++) { if (sum[end] - sum[start] == k) count++; } } return count; } }

Complexity Analysis

Time complexity : O(n^2)O(n​2​​). Considering every possible subarray takes O(n^2)O(n​2​​) time. Finding out the sum of any subarray takes $O(1)$ time after the initial processing of $O(n)$ for creating the cumulative sum array.

Space complexity : $O(n)$. Cumulative sum array $sum$ of size $n+1$ is used.

---

Approach #3 Without space [Accepted]

Algorithm

这个解法跟我的解法是一样的。选择一个特定的$start$ 点，遍历其之后的 $end$ 点。计算从 start ~ end 的 sum。当 $sum$ = $k$ 时，更新 $count$ 值。

Java

public class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum=0; for (int end = start; end < nums.length; end++) { sum+=nums[end]; if (sum == k) count++; } } return count; } }

Complexity Analysis

Time complexity : O(n^2)O(n​2​​). We need to consider every subarray possible.

Space complexity : $O(1)$. Constant space is used.

---

Approach #4 Using hashmap [Accepted]

Algorithm

we know the key to solve this problem is SUM[i, j]. So if we know SUM[0, i - 1] and SUM[0, j], then we can easily get SUM[i, j]. To achieve this, we just need to go through the array, calculate the current sum and save number of all seen PreSum to a HashMap. Time complexity O(n), Space complexity O(n).

Java

public class Solution { public int subarraySum(int[] nums, int k) { int sum = 0, count= 0; Map<Integer, Integer> preSum = new HashMap<>(); preSum.put(0, 1); for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (preSum.containsKey(sum - k)) { count += preSum.get(sum - k); } preSum.put(sum, preSum.getOrDefault(sum, 0) + 1); } return count; } }

Complexity Analysis

Time complexity : $O(n)$. The entire $nums$ array is traversed only once.

Space complexity : $O(n)$. Hashmap $map$ can contain upto $n$ distinct entries in the worst case.