0.总结

• 冷静分析，快速答题
• O(n)时间复杂度解决
• 博客来源：LawsonAbs@CSDN

1.题目

直接的想法则是：使用排序，降数组排序，然后看哪些数在正确的位置上，除此之外的，都是需要重排的。但题这么做就没难度了。
本题的难点在于如何使用O(n)的时间复杂度。 我最开始的想法有点儿过于复杂。我在从左往右找最大时，记录了每次遇到的最大值，得到一个数组。然后再根据这个数组判断上界是在什么位置，但是这么考虑就会导致相等的数无法判断。
[2,6,4,8] 和 [2,4,4,8]从右往左更新得到的数组都是一样的，都是[2,4,4,8]。这个失败的地方就在于：你丢失了这个数原本和最小数间的大小关系。
直接点儿，我就想到，那能不能不要用这个中间数组，我们直接一次性到位，在遍历获取最小值的同时，记录逆序的位置。这样既可以保留原来的大小关系，也可以得到下标信息。

2.思想

• 从左到右找最大时，如果遇到当前的数比最大数小，则更新下标
• 从右往左找最小时，如果遇到当前的数比最小数大，则更新下标

3.代码

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        # 从左往右更新最大        
        cur_max = nums[0]
        max_idx = 0 
        for i in range(len(nums)):
            if cur_max <= nums[i]:                
                cur_max = nums[i]
            else:
                max_idx = i

        # 从右往左更新最小        
        cur_min = nums[-1]
        min_idx = len(nums)-1
        for i in reversed(range(0,len(nums))):
            if cur_min >= nums[i]:
                cur_min = nums[i]
            else:
                min_idx = i
        
        # print(min_idx,max_idx)
        if min_idx >= max_idx:
            return 0
        return max_idx-min_idx+1