581. Shortest Unsorted Continuous Subarray

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

Python

因為題目最終需要的是遞增排序 拿原本的array去比對排序後的array 用max/min算出左右界

但要是題目不知道最終會是遞增或遞減...可能只能暴力破

• Time: O(NlogN), for the sorting
• Space: O(N), for the sorted array

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        sorted_nums = sorted(nums[:])
        start, end = len(nums)-1, 0

        for i in range(len(nums)):
            if nums[i] != sorted_nums[i]:
                start = min(start, i)
                end = max(end, i)

        diff = end - start
        return diff+1 if diff > 0 else 0