560. Subarray Sum Equals K - Medium

前往題目

想法

• Subarray的話應該還是需要backtracking

思路

這題反而不用backtracking，而是用prefix sum

1. 一個prefix sum表，紀錄每個sum出現的次數
2. 每次都看當前需要多少才能達到k，檢查表中有沒有該sum，有的話就可以直接加到result了因為代表前面的這個sum再加上當前index的數值就等於我們要的k
3. 出現新的sum就放到表中

這部分照著例子，操作一遍演算法就可以理解了，但是腦袋一樣需要轉彎…

Code

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

        for (int num : nums) {
            // Increase by num
            curSum += num;
            // Difference to the k
            int diff = curSum - k;
            // Add to the result
            res += prefixSums.getOrDefault(diff, 0);
            // Add to the prefix sum
            prefixSums.put(curSum, 1 + prefixSums.getOrDefault(curSum, 0));
        }

        return res;
    }
}

2024/05/06

• failed