【刷穿 LeetCode】最短无序连续子数组 :「双指针 + 排序」&「双指针 + 线性扫描」｜ 8月更文挑战

题目描述

这是 LeetCode 上的 581. 最短无序连续子数组 ，难度为 中等。

Tag : 「排序」、「双指针」

给你一个整数数组 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^4104
  
• -10^5105 <= nums[i] <= 10^5105
  
• 进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

双指针 + 排序

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

代码：

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;
    }
}
复制代码

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

双指针 + 线性扫描

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

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

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

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

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

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

代码：

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;
    }
}
复制代码

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

最后

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

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

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

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