LeetCode Subarray Sum Equals K

原題鏈接在這里：https://leetcode.com/problems/subarray-sum-equals-k/description/

題目：

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:

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

題解：

計算subarray的和為k的個數.

保存從頭到當前值和sum 以及 對應這個和的個數. 若是之前出現了sum-k說明這一段相加就是k. 更新和.

Note: 初始HashMap<Integer, Integer> hm 時需要先把和為0的情況加進去. 最開始什么都沒有, 所以hm需要加上<0,1>這個對應關系.

Time Complexity: O(nums.length).

Space: O(nums.length).

AC Java:

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

類似Two Sum,?Continuous Subarray Sum,?Subarray Product Less Than K.