你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

LeetCode最短无序连续子数组

2021/12/9 22:21:29

题目:来自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说明数组有序,不需要调整
    }

感觉这个题,就是来证明我又多垃圾的~~蒟蒻