581. 最短无序连续子数组

本文主要是介绍581. 最短无序连续子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

提示：

1 <= nums.length <= 104
-105 <= nums[i] <= 105

**进阶：**你可以设计一个时间复杂度为 O(n) 的解决方案吗？

解答

class Solution {
public:int findUnsortedSubarray(vector<int>& nums) {// 将数组分三段，左段和右段是标准的升序数组// 中段无序，但最小值大于左段最大值，最大值小于右段最小值// 则目标就是找中段的左右边界 L和R// nums[R] 不可能是[L, R]中最大值(否则应该将nums[R]并入右段数组)// nums[L] 不可能是[L, R]中最小值(否则应该将nums[L]并入左段数组)// 故有， [L, R]中最大值等于[0,R]中最大值， 设其为max// [L, R]中最小值等于[L, nums.length - 1]中最小值， 设其为min// 有nums[R] < max < nums[R + 1] < nums[R + 2]<....，所以从左往右最后一个小于前面的max的值右边界// nums[L] > min > nums[L - 1] > nums[L - 2] >... 所以从右往左最后一个大于后面min的为左边界int len = nums.size();int min = nums[len - 1];int max = nums[0];int begin = 0, end = -1;for(int i = 0; i < len; i++){// 从左往右最后一个小于max的为右边界if(nums[i] < max){end = i;}else {max = nums[i];}// 左段不会进这个判断if(nums[len - i - 1] > min){begin = len - i - 1;}else {min = nums[len - i - 1];}}return end - begin + 1;}
};