[LeetCode] 209.最小サイズのサブアレイ合計問題解決レポート（Python）

209 Minimum Size Subarray Sum Problem Solving Report

著者：Xue MingZhuネガティブ
id：fuxuemingzhu
個人ブログ： http://fuxuemingzhu.cn/

---

トピックアドレス： https://leetcode.com/problems/minimum-size-subarray-sum/description/

トピックの説明：

nの配列が与えられます正の整数と正の整数sは、contiguousの最小の長さを見つけます。 sum ≥ sのサブ配列。存在しない場合は、代わりに0を返します。

例：

Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint.

ファローアップ：
O（n）ソリューションを理解した場合は、時間計算量がO（n log n）である別のソリューションをコーディングしてみてください。

局所

合計が> = sである配列内の最短の連続サブ配列を見つけます。

問題解決方法

今日、「チャレンジングプログラミングコンペティション」という本でこの質問を見たことがあります。この解決策は昆虫法と呼ばれ、実際にはダブルポインターです。実際、2つのサブポインターの多くは、隣接するサブアレイが次のような特定の条件を満たすことを確認するために使用されます。 713.K未満のサブアレイ製品 。

この質問には最小値が必要なため、結果はinfに初期化され、そのたびに右ポインターが移動します。条件が満たされると、結果が更新され、左ポインタが移動され、左桁が記憶されます。

時間計算量はO（N）であり、空間計算量はO（1）です。

class Solution: def minSubArrayLen(self, s, nums): ''' :type s: int :type nums: List[int] :rtype: int ''' N = len(nums) l, r = 0, 0 csum = 0 res = float('inf') while r < N: csum += nums[r] while csum >= s: res = min(res, r - l + 1) csum -= nums[l] l += 1 r += 1 return res if res != float('inf') else 0

参考資料：

日付

2018年10月15日-美しい月曜日にスモッグが発生する可能性はありますか？