[581] Shortest Unsorted Continuous Subarray | LeetCode Medium

🔎 문제설명

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.

오름차순으로 배열을 정렬할 때, 주어진 배열에서 연속적으로 수정해야하는 수를 구하는 문제입니다.

Example 1

Input: nums = [2,6,4,8,10,9,15]
Output: 5

[6, 4, 8, 10, 9]만 정렬해주면 전체배열이 오름차순이 됩니다.

Example 2

Input: nums = [1,2,3,4]
Output: 0

Example 3

Input: nums = [1]
Output: 0

제한사항

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

---

접근법은 투 포인터 탐색 알고리즘을 사용하는 것입니다.

한 포인터는 배열의 맨 앞부터 나머지 하나는 맨 뒤부터 탐색을 하면서 정렬이 아닌 인덱스들을 찾습니다.
그리고 두 인덱스의 차이를 반환합니다.

🧊 파이썬 코드

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        sortedNums = sorted(nums)	#비교를 위해 정렬된 배열을 생성
        start, end = -1, -1
        
        i = 0
        while(i < len(nums)):
            if nums[i] != sortedNums[i]: #달라진 지점을 기록
                start = i
                break
            i += 1
        if start == -1: return 0 #start가 변화가 없으면 nums는 처음부터 정렬된 상태
        
        i = len(nums) - 1
        while(i >= 0):
            if nums[i] != sortedNums[i]:
                end = i
                break
            i -= 1
        return end - start + 1