请人做网站卖东西好吗,曹县建设局网站,软文营销的步骤,简单门户网站开发题目链接
最短无序连续子数组
题目描述 注意点
找出符合题意的 最短 子数组#xff0c;并输出它的长度-100000 nums[i] 100000
解答思路
本题的数组可以分为三段#xff0c;左段中段和右段#xff0c;如下图所示 观察规律可知#xff0c;左段元素始终比中段…题目链接
最短无序连续子数组
题目描述 注意点
找出符合题意的 最短 子数组并输出它的长度-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;}
}关键点
双指针的思想怎么找到中段的左右边界
