[LeetCode] 581 | Shortest Unsorted Continuous Subarray | Python

---

문제 링크: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

---

문제

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

---

조건

• 1 <= nums.length <= $10^4$
• $-10^5$ <= nums[i] <= $10^5$

---

내 풀이

앞에서부터 탐색하며 순서가 맞지 않는, 가장 큰 index를 찾는다.

뒤에서부터 탐색하며 순서가 맞지 않는, 가장 작은 index를 찾는다.

두 index 사이의 리스트를 다시 정렬하면 된다.

---

코드

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        mini, maxi = nums[0], nums[-1]
        left, right = len(nums)-1, 0
        
        for idx, num in enumerate(nums):
            if num < mini:
                right = idx
            else:
                mini = num
        
        for idx in range(len(nums)-1, -1, -1):
            num = nums[idx]
            if num > maxi:
                left = idx
            else:
                maxi = num
                
        if right > 0:
            return right - left + 1
        else:
            return 0