數組4
- 1、長度最小的子數組（209）
- 2、無重複字元的最長字串（3）
- 3、找到字元串中所有字母異位詞（438）
- 4、最小覆寫字串（76）
————技巧點：滑動視窗
1、長度最小的子數組（209）
題目描述：
【中等題】
給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的 連續 子數組，并傳回其長度。如果不存在符合條件的子數組，傳回 0。
題目連結
思路分析：
要求：求其和 ≥ s \geq s ≥s的最小連續子數組長度
求解子數組問題時，需要先搞清楚以下幾個問題：
-
連續不連續，如果是連續，有沒有元素大小的情況？
題目中是連續的子數組，且不用考慮元素的大小情況。
-
沒有解的情況需不需要考慮？
題目中沒有解的情況，預設傳回為0。怎麼判斷沒有解，可以在開始設定初始值，最後判斷如果初始值不變的話，就傳回0.
-
傳回的是什麼？是子數組，還是子數組長度？
如果是隻傳回長度值，就不用考慮多組解的情況。如果是傳回最短子數組，就要考慮多組解的情況–如果是要隻傳回某一個解，那麼這個解有什麼限定？如果是要傳回多個解，那麼這多個解按什麼順序來傳回？
題解一：暴力法：雙層周遊
- 初始化子數組的最小長度為無窮大或者len+1(最小長度不可能超過這個的）
- 枚舉數組 nums \text{nums} nums 中的每個下标作為子數組的開始下标，對于每個開始下标 i，需要找到大于或等于i 的最小下标j，(第二次周遊開始）使得從 nums [ i ] \text{nums}[i] nums[i] 到 nums [ j ] \text{nums}[j] nums[j]的元素和大于或等于 s，并更新子數組的最小長度（此時子數組的長度是 j-i+1）。
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
ans = n + 1#初始化最小長度
for i in range(n):
total = 0
for j in range(i, n):
total += nums[j]
if total >= s:
ans = min(ans, j - i + 1)#更新最小長度
break
return 0 if ans == n + 1 else ans
- 時間複雜度： O ( N 2 ) O(N^2) O(N2)
- 空間複雜度： O ( 1 ) O(1) O(1)
這種方法時間複雜度為 O ( N 2 ) O(N^2) O(N2),時間太長，不建議這種方法，并且python語言實作會出現超出時間限制這一問題。
題解二：滑動視窗法
\quad \quad 在上一題解中，其中包含了大量的重複計算，對于nums[i,j]到nums[i+1,j]的和，隻需要減去nums[i]即可，但是剛剛的操作是又通過一遍數組來通過。如何避免這種重複操作呢？其實，從這到那就是一個滑動的過程，将子數組
nums[i,j]
定義一個視窗，根據具體情況具體滑動。針對本題，具體過程如下：
- 初始化視窗：即初始化指針l=0，r=-1
- 初始累加和total=0
- 初始最小長度res為其達不到的最大值len+1
- 移動指針/滑動找到可行解并優化執行以下操作：
- 找到可行解：如果和小于s,則右指針right不斷向右移動，擴張視窗，直到sum和大于等于s，
- 當和大于s，如果此時擴張視窗，條件依然滿足，但背離“最小長度”的要求。是以選擇收縮視窗，優化可行解，
和-nums
- 如果和大于等于s,則此時視窗長度是一個可行解，更新最小長度為其最小值。
- 如果最小長度還是初始值，則無解，傳回0
- 傳回res
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
#[nums[l]...nums[r]]為滑動視窗，初始其無效
l,r=0,-1
#初始累加和為0
total=0
#記錄目前尋找到最小長度，因求最小，故初始化為最大值（不可能取到這個值）
res=len(nums)+1
# 滑動視窗的左邊界小于len,這是充分條件，這樣右邊界才可以取值
while l<len(nums):
'''
對于數組問題而言，一旦用方括号來取值的話，一定要注意數組越界的問題：
需要保證r還在取值範圍内，是以在條件需要進行限定，因l限定到len-1,故r需小于len-1
'''
if r<len(nums)-1 and total<s:
#擴大視窗
r+=1
total+=nums[r]
else:
total-=nums[l]
l+=1
if total>=s:
res=min(res,r-l+1)
if res==len(nums)+1: #無解
return 0
return res
- 時間複雜度： O ( n ) O(n) O(n)
- 空間複雜度： O ( 1 ) O(1) O(1)
2、無重複字元的最長字串（3）
題目描述：
【中等題】
給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。
題目連結
思路分析：
其實就是一個隊列,比如例題中的 abcabcbb，進入這個隊列（視窗）為 abc 滿足題目要求，當再進入 a，隊列變成了 abca，這時候不滿足要求。是以，我們要移動這個隊列！
如何移動？
我們隻要把隊列的左邊的元素移出就行了，直到滿足題目要求！
一直維持這樣的隊列，找出隊列出現最長的長度時候，求出解！
【python3代碼實作】
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
left=0 # 初始化左指針
lookup=set()# 存放已經周遊過的字元
max_len=0
cur_len=0 # 初始化最大長度以及目前長度為0
for i in range(len(s)):
cur_len+=1
while s[i] in lookup:
lookup.remove(s[left])# 移除最左邊元素
left+=1
cur_len-=1
if cur_len>max_len:
max_len=cur_len
lookup.add(s[i])
return max_len
3、找到字元串中所有字母異位詞（438）
題目描述：
【中等題】
給定一個字元串 s 和一個非空字元串 p，找到 s 中所有是 p 的字母異位詞的子串，傳回這些子串的起始索引。
字元串隻包含小寫英文字母，并且字元串 s 和 p 的長度都不超過 20100。
說明：
- 字母異位詞指字母相同，但排列不同的字元串。
- 不考慮答案輸出的順序。
題目連結
思路分析：
【python 3 代碼實作】
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
res=[] # 存放結果
needs={} # 以字典的形式存儲目标字元串中各個字元的數量
windows={} # 記錄視窗中各個字元的數量
for c in p:
needs[c]=needs.get(c,0)+1
length=len(p)
limit=len(s)
left=right=0 # 左右指針，代表視窗的左右邊界
while right<limit:
c=s[right]
if c not in needs: #當遇到不需要的字元時
windows.clear() # 将之前統計的資訊清空
left=right=right+1
else:
windows[c]=windows.get(c,0)+1 #統計目标字元出現的次數
if right-left+1==length: #如果視窗長度等于目标字元串長度，則有可能是字母異位詞
if windows==needs: # 如果視窗字典與目标字典完全一樣，則是字母異位詞
res.append(left) # 将起始索引添加到結果中
windows[s[left]]-=1 # 視窗函數起始索引所對應的元素的計數減一
left+=1 # 左指針向右移一位
right+=1 # 右指針向右移動一位
return res
- 時間複雜度： O ( l e n ( s ) ) O(len(s)) O(len(s))
- 空間複雜度： O ( l e n ( p ) ) O(len(p)) O(len(p))
python dict.get()
4、最小覆寫字串（76）
題目描述：
【困難題】
給你一個字元串 S、一個字元串 T 。請你設計一種算法，可以在 O(n) 的時間複雜度内，從字元串 S 裡面找出：包含 T 所有字元的最小子串。
題目連結
未完待續 一天一道