我来给你讲解 LeetCode 第 581 题：最短无序连续子数组。

题目描述

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

要求：找出满足条件的最短连续子数组，并返回该子数组的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：只需要对 [6,4,8,10,9] 进行升序排序，整个数组就会变为升序。

示例 2：

输入：nums = [1,2,3,4]
输出：0
解释：数组已经是有序的，不需要排序任何子数组。

解题思路分析

这个问题看似复杂，但通过分析数组的特性，可以找到高效的解决方案。

关键观察

1. 有序数组的特征：在完全有序的数组中，每个元素都应该大于等于前一个元素，且小于等于后一个元素。

2. 无序子数组的位置：无序子数组通常出现在数组的中间部分，因为两端的元素可能已经处于正确位置。

3. 边界确定：我们需要找到无序子数组的起始位置和结束位置。

解题步骤详解

方法一：排序比较法（直观但非最优）

思路：将原数组排序，然后比较原数组和排序后数组的差异。

步骤：

1. 复制原数组并排序
2. 从左往右找到第一个不同的位置（无序子数组的起始位置）
3. 从右往左找到第一个不同的位置（无序子数组的结束位置）
4. 计算子数组长度

时间复杂度：O(n log n)，空间复杂度：O(n)

方法二：一次遍历法（最优解）

思路：通过一次遍历同时找到无序子数组的左右边界。

步骤：

步骤1：初始化变量

n = len(nums)
max_val = nums[0]  # 从左到右遍历时的最大值
min_val = nums[n-1] # 从右到左遍历时的最小值
left = -1          # 无序子数组的左边界
right = -1         # 无序子数组的右边界

步骤2：从右往左遍历，找到左边界

• 我们从右往左遍历，记录遇到的最小值
• 如果当前元素大于最小值，说明这个位置需要被包含在无序子数组中

for i in range(n-1, -1, -1):
    if nums[i] > min_val:  # 当前元素大于右边的最小值，需要调整
        left = i
    else:
        min_val = min(min_val, nums[i])  # 更新右边的最小值

步骤3：从左往右遍历，找到右边界

• 我们从左往右遍历，记录遇到的最大值
• 如果当前元素小于最大值，说明这个位置需要被包含在无序子数组中

for i in range(n):
    if nums[i] < max_val:  # 当前元素小于左边的最大值，需要调整
        right = i
    else:
        max_val = max(max_val, nums[i])  # 更新左边的最大值

步骤4：计算结果

if left == -1:  # 数组已经有序
    return 0
else:
    return right - left + 1

完整代码实现

def findUnsortedSubarray(nums):
    n = len(nums)
    if n <= 1:
        return 0
    
    max_val = nums[0]
    min_val = nums[n-1]
    left = -1
    right = -1
    
    # 从右往左找左边界
    for i in range(n-1, -1, -1):
        if nums[i] > min_val:
            left = i
        else:
            min_val = nums[i]
    
    # 从左往右找右边界
    for i in range(n):
        if nums[i] < max_val:
            right = i
        else:
            max_val = nums[i]
    
    if left == -1:  # 数组已经有序
        return 0
    
    return right - left + 1

示例演示

以 nums = [2,6,4,8,10,9,15] 为例：

步骤1：从右往左找左边界

• i=6: nums[6]=15 > min_val=15 → left=-1, min_val=15
• i=5: nums[5]=9 > min_val=9 → left=5, min_val=9
• i=4: nums[4]=10 > min_val=9 → left=4, min_val=9
• i=3: nums[3]=8 > min_val=8 → left=3, min_val=8
• i=2: nums[2]=4 > min_val=4 → left=2, min_val=4
• i=1: nums[1]=6 > min_val=4 → left=1, min_val=4
• i=0: nums[0]=2 > min_val=2 → left=0, min_val=2

步骤2：从左往右找右边界

• i=0: nums[0]=2 < max_val=2 → right=-1, max_val=2
• i=1: nums[1]=6 < max_val=6 → right=-1, max_val=6
• i=2: nums[2]=4 < max_val=6 → right=2, max_val=6
• i=3: nums[3]=8 < max_val=8 → right=3, max_val=8
• i=4: nums[4]=10 < max_val=10 → right=4, max_val=10
• i=5: nums[5]=9 < max_val=10 → right=5, max_val=10
• i=6: nums[6]=15 < max_val=15 → right=6, max_val=15

结果：right=5, left=1 → 长度 = 5-1+1 = 5

算法复杂度分析

• 时间复杂度：O(n)，只需要两次遍历
• 空间复杂度：O(1)，只使用了常数级别的额外空间

这种方法既高效又优雅，是解决此类问题的最佳方案。