昨日回顧
上一篇文章，我們講解了數(shù)據(jù)結(jié)構(gòu)的分類，并對于學(xué)習(xí)到的第一種數(shù)據(jù)結(jié)構(gòu)--數(shù)組進(jìn)行了簡單介紹。
在介紹解題時(shí)，向大家簡述了雙指針的解題思路。指針的解題思路一般分為三類：
- 首尾指針：范圍查找，比如二分搜索等
- 滑動窗口：指針處在數(shù)組同一方向，根據(jù)條件移動左右指針，用于獲取范圍和等
- 快慢指針： 多用于鏈表計(jì)算時(shí)，判斷是否有環(huán)等
那么今天針對滑動窗口的延伸，會再提供兩道題目供大家深入理解。
滑動窗口解題模板
不同于咱們第一章學(xué)習(xí)的整數(shù)那般沒有規(guī)律，滑動窗口可是有模板可套的。通過模板我們可以快速完成解題，但前提是，首先你要知道，題目屬于滑動窗口的解題范圍。那么滑窗的題目怎么識別呢？一般題目中都會有明確的“連續(xù)子數(shù)組”、“連續(xù)子串”等關(guān)鍵字，另外可能會附帶最大、最小的限定詞進(jìn)行補(bǔ)充。
那么遇到這類型題目，該如何思考呢？分為以下幾步：
- 初始化窗口左邊界為0，右邊界可以為0，也可以根據(jù)題意固定大小。
- 我們需要初始化一個(gè)ret的返回值，默認(rèn)為0或者根據(jù)題意默認(rèn)為最大值。
- 最小值根據(jù)題意選擇0 或者Java: Integer.MIN_VALUE ; Python:-float('inf')
- 最大值根據(jù)題意選擇 Java: Integer.MAX_VALUE Python： float('inf')
- 窗口的大小需要根據(jù)題目條件進(jìn)行調(diào)整
- 最大連續(xù)...盡量擴(kuò)張右邊界，直到不滿足題意再收縮左邊界
- 最小連續(xù)...盡量縮小左邊界，直到不滿足題意再擴(kuò)大右邊界
- 在執(zhí)行3操作的過程中，不斷與ret進(jìn)行比較
- 最終返回ret結(jié)果即可。
具體模板如下：
初始化左邊界 left = 0
初始化返回值 ret = 最小值 or 最大值
for 右邊界 in 可迭代對象:
更新窗口內(nèi)部信息
while 根據(jù)題意進(jìn)行調(diào)整：
比較并更新ret(收縮場景時(shí))
擴(kuò)張或收縮窗口大小
比較并更新ret(擴(kuò)張場景時(shí))
返回 ret
下面我就來看一道劍指offer的題目，是否可以通過套模板完成解題。
劍指OfferII008.和大于等于target的最短子數(shù)組
https://leetcode-cn.com/problems/2VG8Kg/solution/shua-chuan-jian-zhi-offer-day06-shu-zu-i-d5ne/
難度：中等
題目
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，
并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。
提示：
- 1 <= target <= 10 ^ 9
- 1 <= nums.length <= 10 ^ 5
- 1 <= nums[i] <= 10 ^ 5
進(jìn)階：
如果你已經(jīng)實(shí)現(xiàn) O(n) 時(shí)間復(fù)雜度的解法, 請嘗試設(shè)計(jì)一個(gè) O(n log(n)) 時(shí)間復(fù)雜度的解法。
示例
示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。
示例 2：
輸入：target = 4, nums = [1,4,4]
輸出：1
示例 3：
輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0
分析
根據(jù)題目，已經(jīng)將剛才提到的關(guān)鍵字進(jìn)行了加粗表示，首先看到連續(xù)子數(shù)組，我們就該考慮是否可以通過滑窗的思維去解題。
然后看到了長度最小的限制，分析題意滑窗思維沒毛病。
那么剛才模板中說的題目條件時(shí)什么呢？滿足滑窗內(nèi)數(shù)字之和需要大于等于target。
返回值ret又是什么？符合條件的子數(shù)組長度。
模板中所有的架子都搭好了，往里面套代碼吧！
解題
Python:
class Solution:
def minSubArrayLen(self, target, nums):
left = total = 0
ret = float('inf')
for right, num in enumerate(nums):
total += num
while total >= target:
ret = min(ret, right - left + 1)
total -= nums[left]
left += 1
return 0 if ret > len(nums) else ret
Java:
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int total = 0;
int ret = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
total += nums[right];
while (total >= target) {
ret = Math.min(ret, right - left + 1);
total -= nums[left++];
}
}
return ret > nums.length ? 0 : ret;
}
}
怎么樣，這道題大家是不可以閉著眼睛套模板 。
有朋友要說了，你這模板是不就是針對這道題寫的，其他題不行吧？
好，那我們來看下一道滑窗的延伸題目，通過分析，一樣可以使用滑窗模板快速解題！
劍指OfferII009.乘積小于K的子數(shù)組
> https://leetcode-cn.com/problems/ZVAVXX/solution/jian-zhi-offerii009cheng-ji-xiao-yu-kde-q158e/
難度：中等
題目
給定一個(gè)正整數(shù)數(shù)組 nums和整數(shù) k ，請找出該數(shù)組內(nèi)乘積小于 k 的連續(xù)的子數(shù)組的個(gè)數(shù)。
提示:
- 1 <= nums.length <= 3 * 104
- 1 <= nums[i] <= 1000
- 0 <= k <= 106
示例
示例 1:
輸入: nums = [10,5,2,6], k = 100
輸出: 8
解釋: 8 個(gè)乘積小于 100 的子數(shù)組分別為: [10], [5],
[2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘積小于100的子數(shù)組。
示例 2:
輸入: nums = [1,2,3], k = 0
輸出: 0
分析
這道題乍一看滿足滑窗的條件，讓我們找小于K的連續(xù)子數(shù)組的個(gè)數(shù)，但這不是求最大最小滑窗的長度，而是要求子數(shù)組的個(gè)數(shù)。有點(diǎn)不滿足公式?。?br>
別著急否定，讓我們來畫個(gè)圖考慮下滑窗右邊界移動這個(gè)操作與滑窗內(nèi)子數(shù)組個(gè)數(shù)的關(guān)系吧！
通過畫圖我們發(fā)現(xiàn)，窗口每次移動后，ret都可以增加right - left + 1個(gè)子數(shù)組。這不就可以通過滑窗來解題了么？
但這里要注意一點(diǎn)：
如果數(shù)組中某個(gè)數(shù)字比K還大，則left會超過right，以保證有值，此時(shí)窗口長度為-1，無需計(jì)算。
注意：由于K<=10 ^ 6，nums[i]<=1000, 10 ^ 9 小于Integer.MAX_VALUE，所以Java使用int類型不會越界。
解題
Python：
class Solution:
def numSubarrayProductLessThanK(self, nums, k):
left = ret = 0
total = 1
for right, num in enumerate(nums):
total *= num
while left <= right and total >= k:
total //= nums[left]
left += 1
if left <= right:
ret += right - left + 1
return ret
Java：
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int left = 0;
int ret = 0;
int total = 1;
for (int right = 0; right < nums.length; right++) {
total *= nums[right];
while (left <= right && total >= k) {
total /= nums[left++];
}
if (left <= right) {
ret += right - left + 1;
}
}
return ret;
}
}
歡迎關(guān)注我的公眾號: 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時(shí)，了解更多python小知識。
我的個(gè)人博客：https://qingfengpython.cn
