PattySung

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

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

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

<解題>

preSum[0] = 0 preSum[1] = nums[0] preSum[2] = nums[1] + preSum[1]

so we can get the sum from index 0 to 1 by preSum[2] - preSum[0] 利用哈希表記錄前綴和以及其出現的次數，通過查找哈希表中是否存在 sum - k 來判斷是否有子數組的和等於 k。這意味著我們在遍歷數組時，不僅計算了當前位置的前綴和，還檢查了是否存在一個之前的前綴和，使得當前前綴和減去該前綴和等於 k，這樣就能確定存在一個子數組的和等於 k。

HashMap<Integer, Integer> arr = new HashMap<>()(前者是累積的總和，後者是出現的頻率)
arr.put(0,1) 出現(sum of 0, once)


class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);

        int sum = 0;
        int ans = 0;
        for (int i =0 ; i < nums.length ; i++){
            sum += nums[i];
            if (map.containsKey(sum-k)){
                ans += map.get(sum-k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

Time：O(n) Space：O(n)

Leetcode-560. Subarray Sum Equals K

<解題>