@@ -0,0 +1,1293 @@
+package array.pre_sum;%0A%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0Apublic class SubarraySumEqualsK %7B%0A%0A    //Difficulty: Medium%0A    //TAG: Snap%0A    //TAG: presum%0A    //TAG: array%0A%0A    /**%0A     * 560. Subarray Sum Equals K%0A     * Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.%0A     *%0A     * Example 1:%0A     * Input:nums = %5B1,1,1%5D, k = 2%0A     * Output: 2%0A     * Note:%0A     * The length of the array is in range %5B1, 20,000%5D.%0A     * The range of numbers in the array is %5B-1000, 1000%5D and the range of the integer k is %5B-1e7, 1e7%5D.%0A     */%0A%0A    /*%0A    Solution:%0A    Use presum array to quick filter subarray sum, use two sum to quick find designated subarray sum%0A%0A    Time: O(n)%0A    Space: O(n)%0A     */%0A%0A    public int subarraySum(int%5B%5D nums, int k) %7B%0A        if (nums == null) return 0;%0A        Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A        int count = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            nums%5Bi%5D += i == 0 ? 0 : nums%5Bi - 1%5D;%0A            //First check if presum%5Bi%5D itself is == k%0A            if (nums%5Bi%5D == k) count++;%0A            count += map.getOrDefault(nums%5Bi%5D - k, 0);%0A            map.put(nums%5Bi%5D, map.getOrDefault(nums%5Bi%5D, 0) + 1);%0A        %7D%0A        return count;%0A    %7D%0A%0A%7D%0A

560. Subarray Sum Equals K