581 最短无序连续子数组（区间问题）

╰+哭是因爲堅強的太久メ 2022-08-31 11:20 153阅读 0赞

**1. 问题描述：**

给你一个整数数组 nums ，你需要找出一个连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。

**示例 1：**

输入：nums = \[2,6,4,8,10,9,15\]  
输出：5  
解释：你只需要对 \[6, 4, 8, 10, 9\] 进行升序排序，那么整个表都会变为升序排序。

**示例 2：**

输入：nums = \[1,2,3,4\]  
输出：0

**示例 3：**

输入：nums = \[1\]  
输出：0

**提示：**  
1 <= nums.length <= 10 ^ 4  
\-10 ^ 5 <= nums\[i\] <= 10 ^ 5  
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray

**2. 思路分析：**

分析题目可以知道如果当前的位置是不用调整的那么排序之后的数字对应位置是相等的，所以最简单的方法是对数组进行排序，然后找到左右两个端点不同的位置计算区间的长度返回即可，时间复杂度为O(nlogn)，有没有更优秀的做法呢？其实是有的，我们知道要想使得排序的区间长度更小那么应该尽可能使得左右两边的端点对应的区间的长度尽可能大，以最左边的区间为例，要想使得左边区间的长度尽可能大那么应该满足两个条件（同理对于右侧区间也是，右侧区间为区间起点大于左边最大的元素）：

*  区间的元素从小到大排序
 *  区间最后一个元素小于等于右侧最小值

所以我们可以从前往后遍历，找到第一个逆序的位置，说明这个位置之前的元素是从小到大排序的，这个第一个条件就满足了，对于第二个条件我们可以在循环中找，使用两层循环即可，区间的最后一个元素是往前移动的，循环中使得当前的区间的最后一个元素小于等于当前遍历的元素，不满足的时候则左边区间终点的位置继续往前移动，最终使得右边的元素的最小值是大于等于左边区间的最后一个元素，同理右边区间也是类似的。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 使得左/右边区间尽可能大
        def findUnsortedSubarray(self, nums: List[int]) -> int:
            l, r = 0, len(nums) - 1
            # 找到左边区间逆序的位置
            while l + 1 < len(nums) and nums[l] <= nums[l + 1]: l += 1
            if l == r: return 0
            # 找到右边区间逆序的位置
            while r - 1 >= 0 and nums[r] >= nums[r - 1]: r -= 1
            for i in range(l + 1, len(nums)):
                # 使得区间终点的位置小于等于右边元素的最小值
                while l >= 0 and nums[l] > nums[i]: l -= 1
            for i in range(r - 1, -1, -1):
                while r < len(nums) and nums[r] < nums[i]: r += 1
            return r - l - 1

from typing import List
    
    
    class Solution:
        def findUnsortedSubarray(self, nums: List[int]) -> int:
            # 先拷贝一下原数组
            nums_sort = nums[:]
            nums_sort.sort()
            i, j = 0, len(nums) - 1
            # 找到不相同的位置
            while i < len(nums):
                if nums[i] == nums_sort[i]:
                    i += 1
                else:
                    break
            if i == j + 1: return 0
            while j >= 0:
                if nums[j] == nums_sort[j]:
                    j -= 1
                else:
                    break
            return j - i + 1