.jpg)
446 字
2 分钟
最短无序连续子数组
.jpg)
题目描述
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
解题思路
- 双指针边界扫描：
- 从左向右扫描，记录非递增结束点（维护当前最大值）
- 从右向左扫描，记录非递减开始点（维护当前最小值）
- 确定无序区间：
- 左边界 = 右向左扫描中第一个破坏递增的位置
- 右边界 = 左向右扫描中第一个破坏递减的位置
- 边界处理：
- 若数组已有序，返回0
关键洞察
- 无序子数组性质：
- 子数组外元素保持升序
- 子数组内最小值 > 左边界外最大值
- 子数组内最大值 < 右边界外最小值
- 双指针高效性：
- 两次遍历即可确定边界（O(n)时间）
- 极值维护：
- 左扫时维护当前最大值确定右边界
- 右扫时维护当前最小值确定左边界
复杂度分析
- 时间复杂度：O(n)
- 两次独立遍历数组
- 空间复杂度：O(1)
- 仅用常数变量存储边界和极值
代码实现
/** * @link {https://leetcode.cn/problems/shortest-unsorted-continuous-subarray} * @param {number[]} nums * @return {number} */var findUnsortedSubarray = function (nums) { const n = nums.length; let left = n, right = 0; let maxn = nums[0], minn = nums[n - 1];
for (let i = 0; i < n; i++) { maxn = Math.max(maxn, nums[i]); if (nums[i] < maxn) right = i; }
for (let i = n - 1; i >= 0; i--) { minn = Math.min(minn, nums[i]); if (nums[i] > minn) left = i; }
return right > left ? right - left + 1 : 0;};