題目：給定一個數(shù)組arr，該數(shù)組無序，但每個值都為正數(shù)，在給定一個正數(shù)k。求arr中所有的子數(shù)組中所有元素累加為k的最長子數(shù)組長度。?
　　例如，arr = [1,2,1,1,1]，k = 3.?
　　累加和為3的最長子數(shù)組為[1,1,1]，所以返回結果為3。

基本思路：

　　使用兩個指針left和right，代表子數(shù)組的范圍，初始時都為 0。使用變量sum記錄子數(shù)組的累加和，初始為arr[0]。即arr[0…0]的累加和。根據(jù)sum與k的比較結果確定指針的移動：

　　?1、如果 sum == k，說明目前子數(shù)組的累加和滿足條件，該子數(shù)組的長度可知 right - left + 1。因為整個數(shù)組元素都是正數(shù)，所以，在擴展該子數(shù)組顯然不可能等于k，所以我們應該令left加1，開始考察以 left + 1 位置開始的子數(shù)組，同時令 sum -= arr[left].

　　?2、如果 sum < k，說明還需要加上 right 后面的元素，所以令right + 1，同時令 sum += arr[right+1]。這里需要注意 right + 1 后是否越界。?
　　?
　　?3、如果 sum > k，說明此時子數(shù)組的累計和已經(jīng)大于k，所以令left + 1 表示開始考慮以 left + 1 開始的子數(shù)組，同時令 sum -= arr[left].
?

def getMaxLength(L,k):if L == None or len(L)<1 or k < 0:return 0left = 0right = 0sum_ = L[0]length = len(L)while right < len(L):if sum_ == k:length = max(length,right-left+1)sum_ -= L[left]left +=1elif sum_ < k:right = right +1if right == len(L):breaksum_ += L[right]else:sum_ -= L[left]left +=1return length

?

總結

以上是生活随笔為你收集整理的未排序正整数组中累加和为指定值的最长子数组长度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。