题目:来自LeetCode
一个数组有序,那么左边的数一定小于右边的数,如果一个数组部分有序,就说明这个平衡在某个地方被打破了,从左向右遍历,如果nums[i]小于左边的max,则说明位置i的元素需要调整,用right保存这个值,遍历整个数组,一直到最后,不断的更新right的值,那么遍历结束得到的下标就是最后一个需要调整的位置,同理,从右向左遍历, 如果nums[i]大于右边的最小值,这说明位置i需要调整,用left来保存这个值。最后right-left+1就是要调整的数的长度。
int findUnsortedSubarray(vector<int>& nums) {
int left=0,right=0;
int n=nums.size();
int max=nums[0];
for(int i=1;i<n;i++){//从左往右遍历,确定右边界
if(nums[i]<max) {right=i;}
else max=nums[i];
}
int min=nums[n-1];
for(int i=n-2;i>=0;i--){//从右往左遍历,确定左边界
if(nums[i]>min){
left=i;
}
else min=nums[i];
}
return right==left?0:right-left+1;//如果最后left=right说明数组有序,不需要调整
}
感觉这个题,就是来证明我又多垃圾的~~蒟蒻