30-Day LeetCoding Challenge Day22: Subarray Sum Equals K

這題題目很短，問我們在一個array裡面，總和為某個數字的subarray有幾個，就這樣。

題目說了，array最可長達2萬，所以O(n²)的暴力解是肯定行不通的。得另外想辦法。

假設我們知道一個array，從0到i的總和、以及0到j的總和，那這兩個值相減，就是subarray[i+1, j]的總和了，對吧？好消息是，我們可以很簡單的用O(n)的時間，算出0到任何元素的總和。

假設我們現在在j的位置，已算出從0至j總和是sum，而目標是k，那麼，如果之前曾經出現過任何一個元素i, 他的「從0至i總和」是sum-k，這就代表subarray[i+1, j]的總和就是k了。因此，把每個元素的「從0至此總和」留下來是必要的。

在上述情況中，如果i不只一個，假設有i1與i2兩個數，都符合條件，那其實就代表subarray[i1+1, j]與subarray[j2+1, j]的總和都是k。因此，不只要留下每個元素的「從0至此總和」，而更應留下「從0至此總和為某個數的次數統計」。

如此一來，我們就把題目轉化成了：在一個array裡面，「從0至此總和的差」為某個數字的元素有幾對？

而轉化後的題目，就跟LeetCode的第一題：Two Sum，有87%像了吧？Two Sum要我們找出的是。在一個array裡面，「加起來的值」為某個數字的那一對元素是誰？

這兩個題目的差別，只在要保存的東西不同，一個要保存「出現過的元素」，一個要保存「所有從0至此總和各出現幾次」。

因此，由Two Sum的Solution得到啟發，得解如下：

public class Solution {

    public int subarraySum(int[] nums, int target) {

        int sum = 0;

        Map<Integer, Integer> sumToFrequency = new HashMap<>();
        sumToFrequency.put(0, 1);

        int counter = 0;

        for (int num : nums) {
            sum += num;

            int diff = sum - target;

            Integer frequency = sumToFrequency.get(diff);
            if (frequency != null) {
                counter += frequency;
            }

            sumToFrequency.put(sum, sumToFrequency.getOrDefault(sum, 0) + 1);

        }

        return counter;
    }
}

Happy Coding！