题目给你一个整数数组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 10sup4/sup-10sup5/sup nums[i] 10sup5/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; } }