寫在前面～

最近朋友面試遇到了這道題

發(fā)來和小媛一起討論的時(shí)候

突然覺得說這是一道雖然簡(jiǎn)單，但是仍然可以討論一下的「medium」題目

決定發(fā)出來分享一下

這道題有比較容易想到的「O（n） 時(shí)間復(fù)雜度」的解法

但是難免有的面試官會(huì)＂精益求精＂

進(jìn)階的詢問是否有「O（n log（n）） 時(shí)間復(fù)雜度」的解法

這就需要大家動(dòng)動(dòng)小腦瓜啦～（其實(shí)也不難想到）

閑話少說～

先來看題～

題目

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。

找出該數(shù)組中滿足 其和 ≥ target 的 長(zhǎng)度最小的 連續(xù)子數(shù)組

［nums＿l， nums＿l＋1， ．．．， nums＿r－1， nums＿r］ ，

并返回其長(zhǎng)度。

如果不存在符合條件的子數(shù)組，返回 0 。

示例 1：

輸入：target ＝ 7， nums ＝ ［2，3，1，2，4，3］

輸出：2

解釋：子數(shù)組 ［4，3］ 是該條件下的長(zhǎng)度最小的子數(shù)組。

示例 2：

輸入：target ＝ 4， nums ＝ ［1，4，4］

輸出：1

示例 3：

輸入：target ＝ 11， nums ＝ ［1，1，1，1，1，1，1，1］

輸出：0

提示：

1 ＜＝ target ＜＝ 109

1 ＜＝ nums．length ＜＝ 105

1 ＜＝ nums［i］ ＜＝ 105

先停在這里

思考一會(huì)兒～

你會(huì)用什么方法呢

一、滑動(dòng)窗口 ／ 雙指針

思路：

· 定義兩個(gè)指針 start 和 end 分別表示子數(shù)組（滑動(dòng)窗口窗口）的開始位置和結(jié)束位置

· 維護(hù)變量 sum 存儲(chǔ)子數(shù)組中的元素和

· 初始狀態(tài)下，start 和 end 都指向下標(biāo) 0，sum 的值為 0

· 每一輪迭代，將 nums［end］ 加到 sum，如果 sum≥s，則更新子數(shù)組的最小長(zhǎng)度，然后將 nums［start］ 從 sum 中減去并將 start 右移，直到 sum＜s，在此過程中同樣更新子數(shù)組的最小長(zhǎng)度

· 在每一輪迭代的最后，將 end 右移。

復(fù)雜度分析：

· 時(shí)間復(fù)雜度：O（n），其中 n 是數(shù)組的長(zhǎng)度。指針 start 和 end 最多各移動(dòng) n 次。

· 空間復(fù)雜度：O（1）。c

二、前綴和 ＋ 二分查找

思路：

· 因?yàn)檫@道題保證了數(shù)組中每個(gè)元素都為正，所以前綴和一定是遞增的，這一點(diǎn)保證了二分的正確性。如果題目沒有說明數(shù)組中每個(gè)元素都為正，這里就不能使用二分來查找這個(gè)位置了。

· 在確定每個(gè)子數(shù)組的開始下標(biāo)后，找到長(zhǎng)度最小的子數(shù)組需要 O（n） 的時(shí)間。

· 如果使用二分查找，則可以將時(shí)間優(yōu)化到 O（logn）。

復(fù)雜度分析：

· 時(shí)間復(fù)雜度：O（nlogn），其中 n是數(shù)組的長(zhǎng)度。需要遍歷每個(gè)下標(biāo)作為子數(shù)組的開始下標(biāo)，遍歷的時(shí)間復(fù)雜度是 O（n），對(duì)于每個(gè)開始下標(biāo)，需要通過二分查找得到長(zhǎng)度最小的子數(shù)組，二分查找得時(shí)間復(fù)雜度是 O（logn），因此總時(shí)間復(fù)雜度是 O（nlon）。

· 空間復(fù)雜度：O（n），其中 n 是數(shù)組的長(zhǎng)度。額外創(chuàng)建數(shù)組 sums 存儲(chǔ)前綴和。

       原文標(biāo)題 : 209 | 長(zhǎng)度最小的子數(shù)組