最短无序连续子数组

Leetcode Link: 581. 最短无序连续子数组 - 力扣（LeetCode）

题目

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

题目解读

求的是数组中的某一段子数组，将这个子数组重新排序后，整个数组就有序了，求得是这个子数组的最小长度

解法一

思路：暴力解法

想象一下，在这个数组 L… R 的范围上，怎么确定这个数组一定是无序的，且最短？

当 nums[L]在这个子数组里不是最小的，且 nums[R]在这个子数组里不是最大的，就说明这个数组一定是无序的，且最短。

每次都要比较大小，有点慢。

题解：

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        L = 0
        R = len(nums)-1
        while(L<R):
            if nums[L] != min(nums[L: R+1]) and nums[R] != max(nums[L: R+1]):
                return R-L+1
            if nums[L] == min(nums[L:R+1]):
                L += 1
            if nums[R] == max(nums[L: R+1]):
                R -= 1
        return 0

解法二

思路：充分利用好”排序”这一要求

题目中我们知道我们的目标是”排序好的数组” 因此我们可以先计算出已经排好序的目标，然后比较出左右分别从哪里开始与目标不相等，即可计算出无序连续子数组的长度。

题解：时间$O(NlogN)$，空间$O(N)$

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        comp = nums.copy()
        comp.sort()
        for L in range(len(nums)):
            if nums[L] != comp[L]:
                break
        for R in range(len(nums)-1, -1, -1):
            if nums[R] != comp[R]:
                break
        return 0 if R-L<=0 else R-L+1

解法三

思路：

题解：

启发和联系