1? 題目描述

2 解題思路

2.1 前綴和+逐元素遍歷

一開始想用前綴和+逐起止坐標來遍歷的方法判斷有沒有符合條件的子數(shù)組。（就是先算出a[0], a[0]+a[1], a[0]+a[1]+a[2]+....這些，然后計算sum(nums[i:j])的時候，只需要算前j個的和 減去 前(i-1)個的和就可以了。但是這樣會超時。

class Solution:def checkSubarraySum(self, nums: List[int], k: int) -> bool:tmp=[0]for i in nums:tmp.append(i+tmp[-1]) #求前綴和#逐起止坐標遍歷for i in range(len(nums)-1):for j in range(i+1,len(nums)):#print(i,j,tmp[j],tmp[i])if((tmp[j+1]-tmp[i])%k==0):return(True)return False

2.2 前綴和+哈希表

換一個思路想，我們記sum(K)是前K個元素的前綴和，那么什么時候sum(nums[i:j])，即sum(j)-sum(i-1)可以被k整除呢？那應(yīng)該是sum(j)和sum(i-1)被k除后的余數(shù)相等。

所以我們可以建立一個哈希表，記錄我們sum到下標為幾的元素時，這些元素的前綴和被k除后的余數(shù)。如果之后的前綴和余數(shù) 和之前存在哈希表中的前綴和余數(shù)相同，那么我們看一下他們分別sum到那個下標了，如果兩個下標的差大于等于2，那么就存在這樣的子數(shù)組。（比如sum(i)和sum(j)的k余數(shù)時一樣的，那么i+1~j這些元素組成的子數(shù)組滿足條件）

有一點需要注意的是，這個哈希表我們得存一個(0,-1),表示我們一個都沒有sum的情況下的前綴和。

class Solution:def checkSubarraySum(self, nums: List[int], k: int) -> bool:dit={0:-1}tmp=0for i in range(len(nums)):tmp=(tmp+nums[i])%kif tmp not in dit:dit[tmp]=ielse:if(i-dit[tmp]>=2):return(True)return False

?

總結(jié)

以上是生活随笔為你收集整理的文巾解题 523. 连续的子数组和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。