[LeetCode 560] Subarray sum equa

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].

Solution： 三种solution，从暴力解到最优解

image.png image.png

        if (nums == null || nums.length == 0)
            return 0;
        
        //1. construct prefixSumList
        int[] prefixSumList = new int[nums.length + 1];
        
        int prefix = 0;
        int index = 1;
        for (int num : nums) {
            prefix += num;
            prefixSumList[index ++] = prefix;
        }
        
        //2. In prefixSum List, for each j, find how many <i,j> ==> sum of subarray (i, j) == prefixSum[j] - prefixSum[i] == k?
        int count = 0;
        Map<Integer, Integer> prefixSumVsFreq = new HashMap<> ();
        prefixSumVsFreq.put (0, 1); // initially put 0 to the prefixSumList before we construct it.
        for (int j = 1; j < prefixSumList.length; j++) {
            int freq = prefixSumVsFreq.getOrDefault (prefixSumList[j] - k, 0);
            count += freq;
            prefixSumVsFreq.put (prefixSumList[j], prefixSumVsFreq.getOrDefault (prefixSumList[j], 0) + 1); 
        }
        
        return count;