Leetcode題解 Python & C#：四月挑戰DAY22 Subarray Sum Equals K

給一串整數數列與整數 k ，請回傳有多少個連續子數列總和為 k 。

看到這種 sum 的問題，心中就先想到 k – sum 是否在某一資料(也許 dict 或 list)內，那資料也是某種 sum。

k – sumA = sumB 利用「交換律」來解。

剛好是連續子數列，加上提示有說到「 sum(i,j) = sum(0,j) – sum(0,i)」，這點出了該如何搭配上交換律。

把出現過的 sum 值保存起來，接著再用 k – sum 去找是否它存在於剛剛保存下來的各sum值內。這是核心的想法。

這裡按照實際撰寫的順序。

先把 0 加入到 memo，其值為 1 ，代表 0 出現過一次。

用一個for迴圈，得到 sum(0, i)，檢查 k – sum(0,i) 是否在 memo 內，如果有則 result += memo[sum(0,i)]。

接著再把 sum(0,i) 加入 memo 中，使 memo 保存各值的出現次數。

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        result = 0
        nsum = 0
        memo = {0:1}
        for num in nums:   
            nsum += num
            if nsum-k in memo:
                result += memo[nsum-k]            
            memo[nsum] = memo.get(nsum, 0) +1
        return result

C#

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        int nsum = 0, result = 0;
        var memo = new Dictionary();
        memo.Add(0,1);
        foreach(int num in nums)
        {
            nsum += num;
            if (memo.ContainsKey(nsum - k))
            {
                result += memo[nsum - k];               
            }
            if (memo.ContainsKey(nsum))
            {
                memo[nsum]++;               
            }
            else
            {
                memo.Add(nsum, 1);
            }
        }
        return result;
    }
}