物以群分 是否存在整除k的連續區間 Continuous Subarray Sum_Leetcode #523 同餘應用

QUI NGUYEN on Unsplash

題目敘述 Continuous Subarray Sum

給定一個整數陣列，請問是否存在一段區間和能夠整除k的連續區間，而且區間長度≥2?

如果存在，返回True。

無果無解，返回False。

例如[2,5,3,1,8,6], k = 6, 其中[3,1,8]是區間和能夠整除6的連續區間，而且區間長度≥2。

測試範例

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

無解，找不到區間和能夠整除​13的區間

觀察 整除與同餘的關係

題目說要找一段區間和能夠整除k的區間，而且區間長度≥2。

先關注在前半段 區間和能夠整除k的區間。

區間和能夠整除k 代表 區間和是k的倍數 代表 區間和除以k餘0

換句話說 區間的頭尾除以k同餘(有相同的餘數)

示意圖

舉一個實際的例子幫助讀者了解，假如k=6

array = [2,5,3,1,8,6]

前綴%k餘數= [2,1,4,5,1,7]

發現同餘1的地方有兩處，對應的整除k的區間為[3,1,8]，區間和 = 12 可以整除 k=6

現在已經知道可以利用前綴除以k同餘的表格來找目標區間，那怎麼保障區間長度≥2呢?

也很簡單，建立一個字典，記錄這個餘數第一次出現的index。

假如之後發現同餘，拿當下的index和表格裡面的index相減，就可以知道是否區間長度≥2

演算法 字典 + 前綴和%k的餘數

建立一個字典，紀錄每個餘數第一次出現的index。

從左到右掃描每個元素，每回合更新對應的前綴和%k的餘數，

假如發現同餘，拿當下的index和表格裡面的index相減，若區間長度≥2，代表找到滿足的區間，返回True。

如果掃描到最後一個元素都無解，則返回False。

程式碼 字典 + 前綴和%k的餘數

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        
        # use maximal integer to represent infinity
        INF = sys.maxsize
        
        # key: remainder of mod k
        # value: leftmost index if we have seen this remainder before
        modulo_dict = { 0:-1 }
        
        # prefix sum of remainder mod k, initialized to 0
        modulo_prefix = 0
            
            
        # scan each number in input array
        for i in range( len(nums) ):
            
            # update prefix sum of remainder mod k
            modulo_prefix = ( modulo_prefix + nums[i] ) % k
            
            
            # check if we have seen this remainder before with index gap >= 2
            if i - modulo_dict.get(modulo_prefix, INF) >= 2:
                return True
            
            
            # update index of current remainder if needed
            if modulo_prefix not in modulo_dict:
                modulo_dict[ modulo_prefix ] = i

        return False

複雜度分析

時間複雜度:O(n)

從左到右依序掃描每個元素，所需時間為O(n)

空間複雜度: O(k)

前綴同餘表格最大尺寸為O(k)，紀錄的是每個前綴同餘0,1,2,...,k-1第一次出現的位置。

關鍵知識點 同餘

從整除k的區間 聯想到等價於 前綴同餘相等的區間。

Reference

[1] Continuous Subarray Sum - LeetCode

回到DP特訓班目錄 和 學習路徑