1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/description/

2.解题方法

2.1.解题思路

思路1：升序排列。在顺序和逆序找到第一个不匹配的位置

思路2：一次遍历。仔细观察可将数组nums分为「前缀升序数组」+「最短无序连续子数组」+「后缀升序数组」，对于「前缀升序数组」中的元素都有nums[i]<=min(nums[i+1:])，所以逆序遍历nums，最后一个不满足该式子的位置就是「最短无序连续子数组」的左边界；同理顺序遍历nums[i]，最后一个不满足nums[i]>=max(nums[:i])的位置就是「最短无序连续子数组」的右边界；通过左边界和右边界的位置即可求出题解

3.解题代码

python3代码

# 思路1：升序排列。在顺序和逆序找到第一个不匹配的位置

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        # 思路2：一次遍历。仔细观察可将数组nums分为「前缀升序数组」+「最短无序连续子数组」+「后缀升序数组」，对于「前缀升序数组」中的元素都有nums[i]<=min(nums[i+1:])，所以逆序遍历nums，最后一个不满足该式子的位置就是「最短无序连续子数组」的左边界；同理顺序遍历nums[i]，最后一个不满足nums[i]>=max(nums[:i])的位置就是「最短无序连续子数组」的右边界；通过左边界和右边界的位置即可求出题解
        n = len(nums)
        i = 0
        maxVal, minVal = -inf, inf
        left, right = -1, -1
        while i < n:
            if nums[i] < maxVal:
                right = i
            else:
                maxVal = nums[i]
            maxVal = max(maxVal, nums[i])
            if nums[n - i - 1] > minVal:
                left = n - i - 1
            else:
                minVal = nums[n - i - 1]
            minVal = min(minVal, nums[n - i - 1])
            i += 1
        return right - left + 1 if left != -1 else 0

4.执行结果