Subarray sum

看似簡單的一題.....其實考點蠻多的

首先，有關 array sum的，幾乎都會用到 prefix sum

算出 prefix sum 後，我們可以想一下，怎樣的情況是某個區間相加為 0?

假設有一個 prefix sum 是 [2, 3, 4, 0, 4, 5]

我們看到 0 ，表示從第一個加到 0 那個位置的和為 0，那這樣就是一組答案

再來，我們發現有重複的兩個數字 4, 4

那麼表示從第一個 4 的後一個元素加到下一個 4 的和為 0

證明： prefix sum = [...Ａ, Ｂ, Ｃ...]

C 是 A 後面元素的和，既然 A = C 那就表示 A 後面的元素加到 C 是 0 啊！

不然Ｃ的結果一定不會跟 A 一樣，這樣又找到另一組解

解法是用一個 map 來看看有沒有重複的元素

有重複，就把儲存起來的 index 當答案，因為儲存起來的 index 表示的是上面的 A，

放進答案時要 +1 ，因為是從後一個開始加的時候為 0

這也是為何一開始要放進 (0, -1) 這組，因為要避免 nums = [0] 跑不過

public List<Integer> subarraySum(int[] nums) {
    List<Integer> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }

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

    int sum = 0;
    for (int i=0; i<nums.length; i++) {
        sum = sum + nums[i];
        if (map.containsKey(sum)) {
            result.add(map.get(sum)+1);
            result.add(i);
            break;
        }
        map.put(sum, i);
    }
    return result;
}

複雜度 O(n)