581. Shortest Unsorted Continuous Subarray

Problem

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

Constraints:

1 <= nums.length <= 10⁴
-10⁵ <= nums[i] <= 10⁵

Follow up: Can you solve it in O(n) time complexity?

Test Cases

1 2	class Solution: def findUnsortedSubarray(self, nums: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([2,6,4,8,10,9,15], 5),
    ([1,2,3,4], 0),
    ([1], 0),

    ([2, 6, 4, 18, 1, 9, 15], 7),
    ([1, 2], 0),
    ([1, 3, 2, 2, 2], 4),
    ([1, 3, 2, 3, 3], 2),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
    assert sol.findUnsortedSubarray(nums) == expected

Thoughts

先从左到右遍历数组，找到第一个比右边数字大的位置，记为 l。如果 l = n - 1 说明数组已经是有序的了，直接返回 0。

再从右到左遍历数组，找到（最右边）第一个比左边数字小的位置，记为 r。

显然至少区间 [l, r] 需要重新排序。

但也有可能范围更大。先找出 nums[l:r+1] 的最小值和最大值，分别记为 sub_min 和 sub_max。

然后从 l 开始向左，找到小于等于 sub_min 的最大数字的位置更新到 l（直接遍历就行，也可以用二分法，总时间复杂度不变，运行时间可能会略少一些）。从 r 向右，找到大于等于 sum_max 的最小数字的位置更新到 r。更新后的区间 [l, r] 就是需要重排的最小区间范围，大小为 r - l + 1。

总的时间复杂度 O(n)，空间复杂度 O(1)。

Code

solution.py

from bisect import bisect_left, bisect_right


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

        sub_min = min(nums[i] for i in range(l, r + 1))
        sub_max = max(nums[i] for i in range(l, r + 1))
        # while l > 0 and nums[l-1] > sub_min: l -= 1
        # while r < n - 1 and nums[r+1] < sub_max: r += 1
        l = bisect_right(nums, sub_min, hi=l)
        r = bisect_left(nums, sub_max, lo=r) - 1

        return r - l + 1

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。