October 30, 2019

560. Subarray Sum Equals K

这道题不能用 sliding window：
💡 Why not use Sliding Window algorithm to solve this ?: Since the numbers can be negative, the sliding window sum can change unpredictably.

使用Array, Hash Table, Prefix Sum 来做：

Sol 0. Naive Brute Force

For every pair (i,j), check sum of nums[i:j] in O(i-j)/O(n) Time = O(n^3), Time Limit Exceeded, Space = O(1)

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

Sol 1. Brute Force + Prefix Sum

Time = O(n^2)

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

Sol 2. Prefix Sum + Hash Table

Sum of subarray(i, j) = prefixSum[j] - prefixSum[i - 1]. e.g. sum of subarray(1, 2) = prefixSum[2] - prefixSum[0].
Using a hash table to store # of a prefix sum occurs so far. Key: prefixSum. Value: number of times prefixSum appear
Keep record that how many times a specific sum appears. Iterate the numbers. Keep the sum, check whether sum - k exists.

Time = O(n), space = O(n)

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

总结：subarray sub 相关问题可以想到 Prefix sum array 解法。