How do I approach the Shortest Unsorted Continuous Subarray problem?

You can solve it efficiently using two-pointer scanning and invariant tracking to identify the smallest subarray that needs sorting.

What is the time complexity of the optimal solution?

The optimal solution typically has a time complexity of O(n), where n is the length of the array.

What if the array is already sorted?

In that case, the length of the subarray to be sorted is 0, as no sorting is needed.

How do I handle edge cases in this problem?

Edge cases, like arrays with one element or already sorted arrays, should be handled by checking for the absence of unsorted segments.

What is invariant tracking, and how does it help solve the problem?

Invariant tracking involves ensuring that the array maintains a sorted order. By tracking where this invariant breaks, you can pinpoint the boundaries of the subarray to sort.

#581

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。示例 1：输入： nums = [2,6,4,8,10,9,15] 输出： 5 解释：你只需要对 [6, 4, 8, 10…

数组双指针栈贪心排序

题目描述

给你一个整数数组 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⁴
-10⁵ <= nums[i] <= 10⁵

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

lightbulb

解题思路

方法一：排序

我们可以先对数组进行排序，然后比较排序后的数组和原数组，找到最左边和最右边不相等的位置，它们之间的长度就是我们要找的最短无序连续子数组的长度。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        arr = sorted(nums)
        l, r = 0, len(nums) - 1
        while l <= r and nums[l] == arr[l]:
            l += 1
        while l <= r and nums[r] == arr[r]:
            r -= 1
        return r - l + 1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should efficiently identify the boundaries of the unsorted subarray using a two-pointer technique.
question_mark
The interviewee should demonstrate how they maintain the invariant during the scanning process.
question_mark
Look for a clear and optimal solution where the candidate explains the reasoning behind their approach.

warning

常见陷阱

外企场景

error
Not updating the pointers correctly when scanning for the unsorted boundaries.
error
Overlooking edge cases, like an already sorted array or a very short array.
error
Confusing the invariant, leading to unnecessary subarray checks or inefficiencies.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to handle arrays that may contain duplicate elements.
arrow_right_alt
Extend the problem by asking to sort the identified subarray and return the fully sorted array.
arrow_right_alt
Introduce constraints on time complexity, such as requiring a solution that operates in O(n log n) or better.

help

常见问题

外企场景

继续练习

#768 最多能完成排序的块 II #769 最多能完成排序的块 #321 拼接最大数