560. Subarray Sum Equals K

560. Subarray Sum Equals K

Given an array of integers nums 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

Example 2:

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

Constraints:

• 1 <= nums.length <= 2 * 10e4

• -1000 <= nums[i] <= 1000

• -107 <= k <= 107

My Solutions:

方法1：用两个for loop，对每一个数，找到所有的连续subarray

Time: O(n^2); Space: O(1)

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        
        int res = 0;
        
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) res++;
            }
        }
        return res;
    }
}

方法2：

在Naive的解法中，计算subarray的和的时候，每次都需要遍历该subarray中的每个数，有很多重复的计算。减少重复的一个方法，就是把之前已经计算过的subarray(i, j)的和保存下来，当j++的时候我们只需要在原来的和的基础上加上新的nums[j]

比如

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

prefixSum[x] = sum of subarray(0, x) = nums[0] + nums[1] + ... + nums[x]

index: 0 1 2

nums = [1,1,1]

prefixSum = [0,1,2,3]

通过这个prefixSum array，就可以用O(1)的时间求出任意一个subarray的和

这个问题转化为 for each j：how many i < j satisfies prefixSum[i] = prefixSum[j] - k. 对于每个j，需要记录之前所有的prefixSum，然后在这些prefixSum中查找有多少个数值等于 prefixSum[j] - k

用一个hashmap保存以下，map需要先加一个（0，1）进去，代表已经有一个可以达到presum=0的解法。

• key：prefixSum value

• value： number of occurrences of the prefixSum value

遍历数组求和，当求到一个位置的和的时候，向前找sum-k是否在map中。

• 如果sum-k在map里的，说明有subarray满足条件，count += map.get(sum - k)。

• 无论如何当前这个sum出现的次数多了一次

Time: O(n); Space: O(n)

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