ゼロから始めるLeetCode Day31「581. Shortest Unsorted Continuous Subarray」

概要

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

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

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

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

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day30「234. Palindrome Linked List」
次回
ゼロから始めるLeetCode Day32「437. Path Sum III」

問題

581. Shortest Unsorted Continuous Subarray
難易度はeasy。
Top 100 Liked Questionsからの抜粋です。

問題としては、整数の配列が与えられます。
この配列を昇順で並べ替えると、配列全体を昇順で並べ替えられる連続したサブ配列を見つけてください。
それらの中で最短のサブの配列を見つけ、その長さを返してください、という問題です。

例をみながら考えてみましょう。

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

この中で並べ替えれば配列全体が昇順に整頓されるサブ配列の中最短のものは6から9までですので、その要素数を取得して5を返しています。

解法

ソートした変数と最初から要素を取得する変数startと最後から要素を取得する変数lastを用意し、仮にソート済みの配列と元の配列の値が一致しないならばその要素のインデックスをstartに代入します。それをlastの方でも行い、その差分+1が求められている要素数の長さになります。

最後に、last-startが成り立つならばlast - start + 1を、それ以外は0を返すという関数を実装しました。

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        start = last = 0
        num = sorted(nums)
        for i in range(len(nums)):
            if nums[i] != num[i]:
                start = i
                break
        for i in range(len(nums)-1,-1,-1):
            if nums[i] != num[i]:
                last = i
                break
        return last - start + 1 if last - start else 0
# Runtime: 196 ms, faster than 98.85% of Python3 online submissions for Shortest Unsorted Continuous Subarray.
# Memory Usage: 15.2 MB, less than 5.00% of Python3 online submissions for Shortest Unsorted Continuous Subarray.

かなり単純な考え方でしたが思ったより良さげですね。
Top Liked Questionsのeasyもかなり少なくなってきたので今後はMediumばかりになる気がします。

Hardに関しては、ちゃんと解けるか分かりませんが機会があれば解きます。