企业官网建设流程全解析

题目

给你一个整数数组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<sup>4</sup>
• -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>

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

算法

将给定的数组 nums 表示为三段子数组拼接的形式，分别记作numsA（左侧有序段），numsB（中间乱序段），numsC（右侧有序段）。当我们对整个序列进行排序，numsA 和 numsC 都不会改变。

本题要求我们找到最短的 numsB，即找到最大的 numsA 和 numsC 的长度之和。因此我们将原数组 nums 排序与原数组进行比较，只需要找到乱序段numsB的最左端left和最右端right，长度就是right - left + 1。

假设numsB 在nums中对应区间为[left,right]。

• 正扫找右边界 right：从左向右遍历，维护遍历过的前缀最大值 maxn：
  • 正常递增数组中，当前元素一定 ≥ 左边所有元素的最大值；
  • 如果当前元素 < maxn，说明这个元素位置错位，属于乱序段；
  • 持续更新，最后一个满足「元素 < 前缀最大值」的位置，就是乱序段的最右端。
• 反扫找左边界 left：从右向左遍历，维护遍历过的后缀最小值 minn：
  • 正常递增数组中，当前元素一定 ≤ 右边所有元素的最小值；
  • 如果当前元素 > minn，说明这个元素位置错位，属于乱序段；
  • 持续更新，最靠前的满足「元素 > 后缀最小值」的位置，就是乱序段的最左端

同一轮循环做到两个方向遍历：正扫下标为i，反扫对称下标为n - i - 1

两个方向的遍历进度完全同步，因此可以放在同一个 for 循环里同时计算，不需要写两轮独立遍历。

代码

class Solution { public int findUnsortedSubarray(int[] nums) { int n = nums.length; // 正扫变量：maxn维护前缀最大值，right记录乱序段最右端下标 int maxn = Integer.MIN_VALUE, right = -1; // 反扫变量：minn维护后缀最小值，left记录乱序段最左端下标 int minn = Integer.MAX_VALUE, left = -1; // 一趟循环同时做从左到右、从右到左的对称扫描 for (int i = 0; i < n; i++) { // ===== 正扫：从左到右定位右边界 ===== // 当前元素比前缀最大值小 → 位置错位，属于乱序段，更新右边界 if (maxn > nums[i]) { right = i; } else { // 正常递增，更新前缀最大值 maxn = nums[i]; } // ===== 反扫：从右到左定位左边界 ===== // 对称下标：n-i-1，从末尾往头遍历 int reverseIdx = n - i - 1; // 当前元素比后缀最小值大 → 位置错位，属于乱序段，更新左边界 if (minn < nums[reverseIdx]) { left = reverseIdx; } else { // 正常递增，更新后缀最小值 minn = nums[reverseIdx]; } } // right=-1说明全程没有错位，数组本身有序，返回0；否则返回乱序段长度 return right == -1 ? 0 : right - left + 1; } }