[Leetcode解題] 1248. Count Number of Nice Subarrays

[Leetcode解題] 1248. Count Number of Nice Subarrays - 使用presum+hashtable解

22 June 2024

medium array presum hash hashtable

題目

1248. Count Number of Nice Subarrays

給定一個整數矩陣nums和一個整數k。如果一個連續子陣列包含恰好k個奇數元素，則稱其為漂亮子陣列nice sub-arrays。求全部漂亮子陣列的數量。

解題思路

這題的思路跟523蠻像的，我們都是要使用presum搭配hashtable來解題，這邊還有一些觀察，如果這邊的presum紀錄的是從開始到當前索引的奇數數字數量，那它會是一個遞增數列，舉例來說：

原數列：[1,1,2,1,1,1]

計算開始到當前索引的奇數個數：[1,2,2,3,4,5], k = 3

當我們求出這個數列後，可以搭配hashtable來記錄，每個回合我們要去找num - k有沒有存在於hashtable中，如果有的話，代表可以形成nice sub-arrays，並且可以形成hashtable[num-k]個。

以上面的例子舉例來說，在idx=4, num=4的那個點，若k=3，則要找hashtable中有沒有1(4-3)，有的話則代表有hashtable[1]個nice sub-arrays以4為結尾。

程式碼

class Solution(object):
    def numberOfSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        ht = {0: 1}
        
        num_nice_arr = 0
        cur = 0
        for num in nums:
            if num % 2 == 1:
                cur += 1
            ht.setdefault(cur, 0)
            ht[cur] += 1
            if cur - k in ht:
                num_nice_arr += ht[cur-k]
        return num_nice_arr