Python C++使用prefix sum mod k + hash map解Leetcode523 Continuous Subarray Sum 關注
評論 文字稿
好,各位好,我們來解今天 Leetcode 的問題
今天的問題是 523 題
所謂的 continuous subarray sum
這個問題
它是被標示成為
Native
雖然是中級的問題,但實際上它有相當的難度
好,那我們看一下它的題目
它這裡會給一個整數的陣列
它名稱就叫做
NUMS
然後還有一個整數 K
它要你去傳回它是
真或假
真的話就是說
這 NUMS 它有一個所謂的
good subarray
good subarray 的定義是什麼呢?
它這裡是說
它的長度至少是 2
而且呢
它這些元素的和
也就是說它這個子陣列
subarray 它的元素的和呢
它是 K 的倍數
我們看這裡的例子
比方說這邊例子第一題的話是
23 2
4 6 7
那這邊它的 K 值是給 6
所以在這裡的話
你這個 subarray
2 4
至少 2 跟 4
它就已經是了
你如果再加一個 6 也 OK
或者你全部
加起來
也都是
所以這邊的話
我們知道
第一個例子它是正確的
第二個例子我們看
它這邊
一樣跟前面
稍微不同的是
這邊是 6
23 2 6 4 7
那基本上呢
它全部的整個陣列
整個陣列
它的和
是 42
所以它當然是 6 的倍數
第三個例子基本上它就不行了
K 是 13
那你怎麼去處理都不行
它這邊的 constraint 要特別的注意
那我們這邊是有寫一個 NOT
好
這個 NOT 我們在上面我們也
透過我們的測試我們其實也找到了一些
特別要小心的一些
Test case
基本上我們當然這邊的話就是
前面的 Leekhoff 所說的
它所謂的一個
group sub-array 的一個定義
基本上你就是要了解
那所以我們原則上我們一個考慮
就是我們直接
對它除以 K 的餘數
所以它餘數呢基本上就 0 1
一直到 K 減 1
所以總共是有 K 個
所以我們原則上我們是去考慮
它的 Prefix 上
Mod K
Module K
那
這個在做法上因為它的 constraint 的關係
就是說它這個 numbers 的長度它最長可以到
10 到 5 次方
如果說你是採用
N 平方的 Big O 的 solution
它有可能就超過時間
就可能就 TLE
另外即使說我們這邊用 Prefix 上
Mod K
你用陣列的方式去做
用 Array 的方式去做
那因為它的 constraint
它最大可以到 2 的 31 次方減 1
所以這個如果你用陣列的方式它也不行
它就會超過記憶體
所謂的 MLE
所以
真正的一個解法呢應該是要透過
Prefix 上
Mod K
那同時呢要使用
HashMap
那我們看
我們先試著
怎麼去解這樣的一個問題
好那我們先
用 Python 來解
我們當然已經用 C++ 解過了
好我們第一件事情就是先
N 設為
這個 numbers 的長度
好
那根據他
這個所謂 group subarray 的定義的第一
第一項
它那個 subarray 的那個長度
它必須是大於等於 2
所以當你的 N 如果是小於 2 的話
那沒什麼好說的
當然就直接做 return
force
好
那
根據我們剛剛的一個 note
那所以你要採用適當的資料結構
這邊的話當然就是在
Python 的話
的 HashMap
或者 HashTable 呢
基本上你應該用的是用 Dictionary
所以這邊用
大括弧
就可以
那
所以我們的 Prefix
代表他
計算當中 Prefix sum
他的初始設定為 0
好
那因為我們是透過 Prefix sum
那你當中的一個差也就是說這個
呃
這個 subarray 它元素的和
所以他有可能他的 Prefix sum
他的整個那個 subarray
他是從 0 開始
所以你這個一開始的時候你必須要將
0
把它擺進來
那他如果是從 0 開始的話他
這邊當然是要負1
啊所以就是說他這個
Nod K 的值在加1
那開始起算
好接下來的話我們就透過
for loop
啊搭配
呃
Enumerate
來考量
那 Enumerate 當中當然是擺的是我們的
Numbers
這邊不要忘記冒號
好所以我們的 Prefix
當然我們就是加等於
我們的 X
那我們基本上只考慮
Module K
所以我們這邊都直接
我們就 Prefix
呃除
除的餘數
等於
K 除以 K 的餘數
所以我們就考慮
呃我們的 Prefix 是不是已經是在這個
Dictionary 裡面這個
Nod K 裡面
如果是的話我們其實只要去考慮
呃
他的
呃他的那個 index 啊目前這 index 啊
呃減掉他那個值呢是不是大於 1 就可以
如果
I 是大於 Nod K
Prefix
加 1 的話
基本上我們就 return true
好這邊
小心點好
否則的話
呃
也就是說之前你的 Nod K 他都沒有 Prefix
的這樣的 key
好所以基本上你就把他設為目前的
index 的值
好
那這個
我們拉
大一點
然後我們這邊
如果說整個 loop 都跑完你都沒有
發現的話當然就是 return
false
好
那我們
把這個 Nod 的
Test case 整個 copy 過來
Ctrl
D
好
我們看看
他是不是 ok
呃
都 ok
啊這些人有好幾個 test case 是非常的邪惡的
好那我們 submit 看看
好基本上
是 ok 的
啊基本上是 ok 的
那我們再看其他的程式語言
比方說 C++ 的做法
啊那個之前我們也做了啊
這個當然就是跟我們剛剛所說的那個
Python 版本
啊基本上是相同的邏輯
好那我們
也是把它 run 一次
好這邊我們特別要講的是在這個第八行
我們如果要增加速度的話
那我們在這個 Nod 我們這邊
預留空間 N 個
啊他這個在
呃
呃 C++ 當中的他的
HashMap 啊他的運算速度可能會早快一些
好那我們 submit 看看
他的一個結果
哦確實蠻快的
108 毫秒就完成了
那打敗 99.58% 的
C++ 的使用者
好那我們就先談到這裡