ゼロから始めるLeetCode Day106「209. Minimum Size Subarray Sum」

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day105「111. Minimum Depth of Binary Tree」

次回
ゼロから始めるLeetCode Day107「98. Validate Binary Search Tree」

Twitterやってます。

問題

209. Minimum Size Subarray Sum
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、n個の正の整数の配列numsと正の整数sが与えられたとき、連続するnumsの和がsを超える部分配列の最小の長さを求めなさい、というものです。
なお、仮にそのような部分配列が存在しない場合は0を返してください。

解法

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        index,num,low = 0,0,float("inf")
        for i in range(len(nums)):
            num += nums[i]
            while num >= s:
                low = min(low,i-index+1)
                num -= nums[index]
                index += 1
        return low if low != float("inf") else 0
# Runtime: 84 ms, faster than  56.50%  of  Python3  online submissions for  Minimum Size Subarray Sum.
# Memory Usage: 16.4 MB, less than  11.95%  of  Python3  online submissions for  Minimum Size Subarray Sum.

for文を回して用意した変数numの値が与えられた基準値のsを超えるまで加算し続け、超えた時点で
for文の中でnumがsを超えた段階で現在のlow(初期値がinf)とi-index+1のどちらが小さいか、すなわち部分配列の最小値がどちらにあるかを求めます。

ここでの処理はまずinfについて理解してからの方が分かりやすいのでinfについて触れます。

最初に変数を宣言した段階でなぜfloat("inf")を代入しているのか気になった方もいるかもしれません。
これはどちらが最大とか最小の問題を解く時によくある手法の一つで、float("inf")ないしは-float("inf")と言った正の無限大や負の無限大はint型と比較した時にどんな値よりも大きい（小さい）と見做されるのです。

つまり、今回のようなケースの場合、最初にfloat("inf")を宣言した段階で、while文の最初の処理である

low = min(low,i-index+1)

という処理は初回に限り、必ずi-index+1の値が代入されます。
2回目以降は値によって代入される値が変化しますが、必ずこういう処理にしたい時にこう言った正と負の無限大を利用する、というわけなんですね。

また、問題文に仮に存在しない場合は0を返せとあるため、仮に最初の処理が行われない、すなわち部分配列が存在しなかったときの分岐が最後の内包表記に書かれています。

それ以外の処理は特に特筆すべき点はないので、今回はここまで。お疲れ様でした。