目錄
這是Leetcode 2024/2/3 的 Biweekly Contest 123. 第三題。
題目分析
題目
You are given an array nums of length n and a positive integer k.
給你一個長度為n的陣列nums和一個正整數k。
A subarray ofnumsis called good if the absolute difference between its first and last element is exactlyk,in other words, the subarraynums[i..j]is good if|nums[i] - nums[j]| == k.
如果nums的一個子數組中，第一個元素和最後一個元素差的絕對值恰好為k，我們稱這個子數組為好的。換句話說，如果子數組nums[i..j]滿足|nums[i] - nums[j]| == k，那麼它是一個好子數組。
Return the maximum sum of a good subarray of nums. If there are no good subarrays, return 0.
請你返回 nums 中好子數組的最大和，如果沒有好子數組，返回 0。
Example 1:
Input: nums = [1,2,3,4,5,6], k = 1
Output: 11
Explanation: The absolute difference between the first and last element must be 1 for a good subarray. All the good subarrays are: [1,2], [2,3], [3,4], [4,5], and [5,6]. The maximum subarray sum is 11 for the subarray [5,6].
Example 2:
Input: nums = [-1,3,2,4,5], k = 3
Output: 11
Explanation: The absolute difference between the first and last element must be 3 for a good subarray. All the good subarrays are: [-1,3,2], and [2,4,5]. The maximum subarray sum is 11 for the subarray [2,4,5].
Example 3:
Input: nums = [-1,-2,-3,-4], k = 2
Output: -6
Explanation: The absolute difference between the first and last element must be 2 for a good subarray. All the good subarrays are: [-1,-2,-3], and [-2,-3,-4]. The maximum subarray sum is -6 for the subarray [-1,-2,-3].
Constraints:
2 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= k <= 10^9
分析
-
題目對「好數列」的定義：頭尾元素的差值 = k
-
題目要求對數列nums的所有「子數列」中的「好數列」求和，並返回其中最大者。
也就是我們要做兩件事情：
-
判斷好數列
-
對子數列求和
解題思路
解法一、先試試 暴力解(Brute force) 吧!
暴力解的思路很簡單，遍歷nums中的所有子數列，並判斷是否為好數列。若是，便對其求和，並且取其中最大者為答案。
範例程式碼如下：
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
ans = float('-inf')
for i in range(len(nums)):
for j in range(i):
if nums[i]-nums[j]==k or nums[i]-nums[j]==-k:
ans = max(sum(nums[j:i+1]), ans)
return ans if ans!= float('-inf') else 0
暴力解的時間複雜度(見後段分析)為 O(n^3)，所以注定是要吃TLE的。
在暴力解中，我們每找到一組好數列，就重新對其求和。每求一次，就花費O(n)的時間。
但所有的好數列都是nums的子數列。這種情況下，能夠將重複求和的時間從O(n)縮減至O(1)，要依靠 Prefix Sum 的技巧。
Prefix Sum 介紹
Prefix Sum 可以歸類為一種特殊的1-D Dynamical Programming。
顧名思義，我們遍歷一個數列，每遇到一個數，就紀錄「從頭開始到目前這個數為止的總和」。
prefix = [nums[0]]
for n in nums[1:]:
prefix.append(n+prefix[-1])
# 每一步均為累加，總時間複雜度O(n)
需要注意的是，因為是連續的遍歷與求和，這邊的總和不必從頭開始加，而只需要把新的數與前一個數的prefix-sum加起來，就可以得到新的數的prefix-sum。以下為錯誤的做法：
# 這是錯的作法
prefix = []
for i in range(len(nums)):
prefix.append(sum(nums[:i+1]))
# 每一步均為從頭加，總時間複雜度O(n^2)
建立好的Prifix Sum如何幫助我們快速求得子數列的總和呢？
參考以下這個範例：
#index 0 1 2 3 4 5 6 7
arr = [1, 1, 4, 5, 1, 4, 1, 9]
我們先計算其Prefix Sum，可得到：
#index 0 1 2 3 4 5 6 7
arr = [1, 1, 4, 5, 1, 4, 1, 9]
ps = [1, 2, 6,11,12,16,17,26]
若想求數列 index = 2~7的和，只需要計算ps[7] - ps[1] = 26 - 2 = 24
實際算算看：
#index 0 1 2 3 4 5 6 7
arr = [1, 1, 4, 5, 1, 4, 1, 9]
4 +5 +1 +4 +1 +9 = 24
換言之，若想求某個數列第i項~第j項的和，只需要將PrefixSum的第j項減去第i-1項即可。
為什麼可以這樣算呢？想想PrefixSum的定義就懂了：
#index 0 1 2 3 4 5 6 7
ps(1) = [1 +1] 4 5 1 4 1 9 = 2
ps(7) = [1 +1 +4 +5 +1 +4 +1 +9] = 26
ps(7)-ps(1) = [4 +5 +1 +4 +1 +9] = 24
至此，我們了解到：
- 可以在O(n)時間內建立一個1-D array 的 Prefix Sum
- 建立完之後，對任意的index i, j：
[i, j]區間的總和 = ps[j] - ps[i-1]
解法二、暴力解 + prefix sum
試試看吧！使用prefix sum來優化前面的暴力解
前面求prefix sum的舉例有一個小問題：當j>i= 0時，因為i-1 = -1 會導致溢位
我們可以在prefix sum數列的最前端添加一個0來解決這個問題。
注意這時候因為prefix sum整個往後移一格，對於[i, j]區間的總和會變成ps[j+1] - ps[i]。
加上prefix sum之後，原本的暴力解變成這樣：
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
ps = [0]
for n in nums:
ps.append(n+ps[-1])
ans = float('-inf')
for i in range(len(nums)):
for j in range(i):
if nums[i]-nums[j] == k or nums[i]-nums[j] == -k :
ans = max(ps[i+1] - ps[j], ans)
return ans if ans!=float('-inf') else 0
結果如何呢？
什麼？竟然還是TLE？
快還要更快！
加上prefix sum之後，我們的效能從 T = O(n^3) 升級成了 T = O(n^2)
但是Leetcode認為，這還不夠快，もっと早く!
還有哪裡可以優化呢？
如果題目要求的是「列出所有」子數列的總和，那複雜度T = O(n^2)已經是最佳解了。因為我們總要把這些子數列找出來(遍歷所有的i,j pair)之後才能對他們求和嘛。
但等等，題目還真的不是這樣問的。
對所有子數列中的「好數列」，求其總和，並且返回其中的最大值
題目並不關心所有子數列，而只關心其中的「好數列」。
發現了這點之後，我們要如何改進效能呢？
加上hashmap吧！
經過以上的分析，O(n^2)的時間還不夠快，我們需要在O(n)的時間內找出所有的好數列。
原本的做法，我們遍歷了數列nums的所有index pair i、j，但這在本題的情境底下卻是多餘的步驟。
實際上，只要給定一個j，我們馬上能得知要去找哪個i，才會讓nums[i:j+1]是「好數列」(或反過來由i找j)。
考慮以下這個例子：
# index: 0 1 2 3 4
Input: nums = [-1,3,2,4,5], k = 3
若給定 i = 0，請問 j 要是多少，nums[i:j+1]才會是好數列呢？
是 j = 2，對吧！
我們怎麼知道的呢？
因為題目要求的「好數列」，其nums[i] - nums[j]必定是3或者-3
因此，此時 i = 0，nums[i] = -1，則nums[j]必定是 -1+3 或 -1-3 ，也就是2或-4。在nums中沒有-4，只有2 ，其index為2。
換言之：
- 給定任意的index
j - 在
nums[:j]中尋找nums[j] + k與nums[j] - k - 並且求得其index
j - 那麼
nums[i:j+1]就必定是一個好數列
想到這裡，就只剩最後一個問題要解決：
假設我們知道要尋找的nums[i]，要花多少時間才能找到其index i？
你可能會想，搜尋整個nums，需要花O(n)呀！
不過還有一個更快的手段：建立反查表，以空間換取時間。
- 我們預先遍歷整個nums
- 將
nums[i]為 key：i為 value，來建立hashmap - 如此一來，使用
nums[i]來找到i就只需要O(1)的時間了！
解法三、Prefix Sum + Hashmap
讓我們總結一下目前為止的方案：
-
對
nums建立 Prefix Sum ，時間複雜度 O(n) -
對
nums建立nums[i] : i的反查 Hashmap ，時間複雜度 O(n) Python的話就是dict -
在 0~len(n-1) 遍歷
j，用nums[j]計算好陣列的nums[i]，時間複雜度 O(n)- 對每個
j：
- 使用 HashMap 查出
i(規定i < j) ，時間複雜度 O(1) - 使用 PrefixSum 計算
nums[i:j+1]的和，時間複雜度 O(1) - 持續比較並記錄最大的和，時間複雜度 O(1)
- 整個步驟的時間複雜度為 O(n) x O(1) = O(n)
- 對每個
整個算法的複雜度…好耶，就是O(n)啦！
還等什麼呢，快實作看看吧！
from collections import defaultdict as dd
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
# 建立 Prefix Sum
ps = [0]
for n in nums:
ps.append(n+ps[-1])
# 建立 Hashmap
index = dd(list)
for i, n in enumerate(nums):
index[n].append(i)
# 遍歷 nums ：對每個 nums[j] → 計算 nums[i] → 反查 i → 計算nums[i:j+1]的和
ans = float('-inf')
for j, nj in enumerate(nums):
for t in (nj+k, nj-k): # nums[i]可能為nums[j]+k 或 nums[j]-k
if t in index:
for i in index[t]: # i
if i<j: # i 在 j 左邊
# i~j好陣列的和↓
ans = max((ps[j+1]-ps[i]), ans)
return ans if ans!= float('-inf') else 0
解法四、Optimized One-Pass Prefix Sum + Hashmap
看似完美，解法三仍然有一些效能上的浪費，直接submit還是會吃TLE。
(偷偷說筆者Contest就吃了一發T卡在這裡，想說太誇張了吧怎麼可能有O(log n)的解，結果只是時間常數太大啦！)
只好來一一挑出能更優化的小細節：
-
總共遍歷了三次nums，分別是建Prefix、建Hashmap、求解
實際上，這三個動作可以一起做，不需要分別去for loop。
這種對loop次數做常數時間優化的細節，一般稱為 N-pass。N即為loop的次數。
-
由於
nums[i]有可能會重複出現，所以在反查表中筆者又建立了一個list，用來存放所有相同nums[i]的i，因為他們都全都是好陣列，所以在最後的迴圈中一一將其取出來求答案。然而，這些好陣列中，其實有不必計算的！
再回頭看一次我們要的答案：「總和最大」的好陣列。
我們如何求好陣列的總和？
sum(i~j) = ps[j+1] - ps[i]發現了嗎？
唯有 ps[i] 最小，sum(i~j)才會最大
僅管可能有許多個
i具有相同的nums[i]，這些i之中只有ps[i]最小的那個(所代表的好陣列)需要被計算！改善的寫法也很簡單：在輸入hashmap (dict)時，如果這個
nums[i]已經有存放一個i了，就比較兩者的ps[i]，並更新為ps[i]較小的一個即可。
もっと…もっと早く！！
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
ps = [0] # Prefix Sum
index = dict() # HashTable {nums[i] : i}
ans = [] # record sum of 'good array'
for j, n in enumerate(nums):
ps.append(n+ps[-1])
if n+k in index:
ans.append(ps[j+1]-ps[index[n+k]])
if n-k in index:
ans.append(ps[j+1]-ps[index[n-k]])
if n not in index or ps[index[n]] > ps[j]:
index[n] = j
return max(ans, default = 0)
看看這令人髮指的 Passing zone，小鼻子小眼睛就是在說你Leetcode啦(誤)
複雜度分析
解法一(暴力解)：時間複雜度O(n^3)
for i T = O(n)
for j x O(n)
sum(i~j) x O(n)
解法二(暴力解+Prefix Sum)：時間複雜度O(n^2)
calculate ps T = O(n)
for i T = O(n)
for j x O(n)
sum(i~j) [by ps] x O(1)
解法三、Prefix Sum + Hashmap：時間複雜度O(n) [時間常數大]
calculate ps T = O(n)
form hashmap T = O(n)
for j T = O(n)
find j [by hashmap] x O(1)
sum(i~j) [by ps] x O(1)
解法四、One-Pass Prefix Sum + Hashmap：時間複雜度O(n) [時間常數小]
for j T = O(n)
x
update ps O(1)
find j [by hashmap] O(1)
sum(i~j) [by ps] O(1)
update hashmap O(1)
本題還有一些Python不太會遇到，但其他語言要注意的陷阱。
例如測資的-10^9 <= nums[i] <= 10^9且2 <= nums.length <= 10^5，某些語言直接計算 prefix sum 時要避免 int overflow 之類的。礙於篇幅就不在此討論了。-其實是筆者不會-
結語
俗話說的好，在哪裡吃T就要在哪裡吃更多的T(不)，希望每一篇Leetcode文都能讓自己更進步！
感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！