LC 581. 最短无序连续子数组

题目描述

这是 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 

示例 3：

输入：nums = [1]

输出：0

提示：

• $1 <= nums.length <= 10^4$

• $-10^5 <= nums[i] <= 10^5$

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

---

双指针 + 排序

最终目的是让整个数组有序，那么我们可以先将数组拷贝一份进行排序，然后使用两个指针 $i$ 和 $j$ 分别找到左右两端第一个不同的地方，那么 $[i, j]$ 这一区间即是答案。

Java 代码：

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) i++;
        while (i <= j && nums[j] == arr[j]) j--;
        return j - i + 1;
    }
}

C++ 代码：

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr(nums);
        sort(arr.begin(), arr.end());
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) ++i;
        while (i <= j && nums[j] == arr[j]) --j;
        return j - i + 1;
    }
};

Python 代码：

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

TypeScript 代码：

function findUnsortedSubarray(nums: number[]): number {
    const n: number = nums.length;
    const arr: number[] = Array.from(nums).sort((a, b) => a - b);
    let i: number = 0, j: number = n - 1;
    while (i <= j && nums[i] === arr[i]) i++;
    while (i <= j && nums[j] === arr[j]) j--;
    return j - i + 1;  
};

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(n)$

---

双指针 + 线性扫描

另外一个做法是，我们把整个数组分成三段处理。

起始时，先通过双指针 $i$ 和 $j$ 找到左右两次侧满足 单调递增 的分割点。

即此时 $[0, i]$ 和 $[j, n)$ 满足升序要求，而中间部分 $(i, j)$ 不确保有序。

然后我们对中间部分 $[i, j]$ 进行遍历：

• 发现 $nums[x] < nums[i - 1]$：由于对 $[i, j]$ 部分进行排序后 $nums[x]$ 会出现在 $nums[i - 1]$ 后，将不满足整体升序，此时我们需要调整分割点 $i$ 的位置；
• 发现 $nums[x] > nums[j + 1]$：由于对 $[i, j]$ 部分进行排序后 $nums[x]$ 会出现在 $nums[j + 1]$ 前，将不满足整体升序，此时我们需要调整分割点 $j$ 的位置。

一些细节：在调整 $i$ 和 $j$ 的时候，我们可能会到达数组边缘，这时候可以建立两个哨兵：数组左边存在一个足够小的数，数组右边存在一个足够大的数。

Java 代码：

class Solution {
    int MIN = -100005, MAX = 100005;
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) i++;
        while (i < j && nums[j] >= nums[j - 1]) j--;
        int l = i, r = j;
        int min = nums[i], max = nums[j];
        for (int u = l; u <= r; u++) {
            if (nums[u] < min) {
                while (i >= 0 && nums[i] > nums[u]) i--;
                min = i >= 0 ? nums[i] : MIN;
            }
            if (nums[u] > max) {
                while (j < n && nums[j] < nums[u]) j++;
                max = j < n ? nums[j] : MAX;
            }
        }
        return j == i ? 0 : (j - 1) - (i + 1) + 1;
    }
}

C++ 代码：

class Solution {
public:
    int MIN = -100005, MAX = 100005;
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) i++;
        while (i < j && nums[j] >= nums[j - 1]) j--;
        int l = i, r = j;
        int minv = nums[i], maxv = nums[j];
        for (int u = l; u <= r; ++u) {
            if (nums[u] < minv) {
                while (i >= 0 && nums[i] > nums[u]) i--;
                minv = i >= 0 ? nums[i] : MIN;
            }
            if (nums[u] > maxv) {
                while (j < n && nums[j] < nums[u]) j++;
                maxv = j < n ? nums[j] : MAX;
            }
        }
        return j == i ? 0 : (j - 1) - (i + 1) + 1;
    }
};

Python 代码：

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n, MIN, MAX = len(nums), -100005, 100005
        i, j = 0, n - 1
        while i < j and nums[i] <= nums[i + 1]:
            i += 1
        while i < j and nums[j] >= nums[j - 1]:
            j -= 1
        l, r = i, j
        minv, maxv = nums[i], nums[j]
        for u in range(l, r + 1):
            if nums[u] < minv:
                while i >= 0 and nums[i] > nums[u]:
                    i -= 1
                minv = MIN if i < 0 else nums[i]
            if nums[u] > maxv:
                while j < n and nums[j] < nums[u]:
                    j += 1
                maxv = MAX if j >= n else nums[j]
        return 0 if j == i else (j - 1) - (i + 1) + 1

TypeScript 代码：

function findUnsortedSubarray(nums: number[]): number {
    const n: number = nums.length, MIN: number = -100005, MAX: number = 100005;
    let i: number = 0, j: number = n - 1;
    while (i < j && nums[i] <= nums[i + 1]) i++;
    while (i < j && nums[j] >= nums[j - 1]) j--;
    const l = i, r = j;
    let minv = nums[i], maxv = nums[j];
    for (let u: number = l; u <= r; u++) {
        if (nums[u] < minv) {
            while (i >= 0 && nums[i] > nums[u]) i--;
            minv = i >= 0 ? nums[i] : MIN;
        }
        if (nums[u] > maxv) {
            while (j < n && nums[j] < nums[u]) j++;
            maxv = j < n ? nums[j] : MAX;
        }
    }
    return j === i ? 0 : (j - 1) - (i + 1) + 1;
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.581 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。