最短无序连续子数组

题目链接

最短无序连续子数组

题目描述

注意点

• 找出符合题意的 最短 子数组，并输出它的长度
• -100000 <= nums[i] <= 100000

解答思路

• 本题的数组可以分为三段，左段中段和右段，如下图所示

• 观察规律可知，左段元素始终比中段小，右段元素始终比中段大，区别是中段中的元素不是严格递增的，所以关键是要找到中段的左右边界
• 将中段的左右边界分别定义为begin和end，进行两次遍历
  • 从左到右维护一个最大值max，在进入右段之前，那么遍历到的nums[i]都是小于max的，end也就是遍历中最后一个小于max元素的位置（进入右端后新的元素始终都比之前维护的max大）
  • 从右到左维护一个最小值min，在进入左段之前，那么遍历到的nums[i]也都是大于min的，begin也就是最后一个大于min元素的位置（进入左端后新的元素始终都比之前维护的min小）

代码

class Solution {public int findUnsortedSubarray(int[] nums) {int n = nums.length;int maxValue = Integer.MIN_VALUE;int minValue = Integer.MAX_VALUE;int begin = 0;int end = -1;for (int i = 0; i < n; i++) {if (nums[i] < maxValue) {end = i;} else {maxValue = nums[i];}}for (int i = n - 1; i >= 0; i--) {if (nums[i] > minValue) {begin = i;} else {minValue = nums[i];}        }return end - begin + 1;}
}

关键点

• 双指针的思想
• 怎么找到中段的左右边界