Leetcode581. 最短无序连续子数组(HOT100)

链接

我的代码：

class Solution {
public:int findUnsortedSubarray(vector<int>& nums) {vector<int> res = nums;sort(res.begin(),res.end());int l = 0,r = nums.size()-1;while(nums[l]==res[l]){++l;if(l==nums.size()){return 0;}}while(nums[r]==res[r]){--r;//这就就不用判断if(r==0)了，因为代码能走到这里说明我们从左到右遍历时遇到了不同的点}return r-l+1;}
};
//https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solutions/2846020/san-chong-jie-fa-duo-yu-yan-you-pei-tu-b-38a4

更好的代码：

class Solution {
public:int findUnsortedSubarray(vector<int>& nums) {int n = nums.size();int l = 0, r=  n-1;while(l+1<n&&nums[l+1]>=nums[l])++l;if(l==n-1)return 0;while(r-1>=0&&nums[r-1]<=nums[r])--r;for(int i = l+1;i<n;i++){while(l>=0&&nums[l]>nums[i])--l;}for(int i = r-1;i>=0;i--){while(r<n&&nums[r]<nums[i])++r;}return r-l-1;}
};

题解：第一种方法很好理解，我们的目标是让整个数组非递减排序。那么我们就拷贝一下原数组，排个序让我们直观地看到最终结果。

然后挨着比较对应位置元素是否相等，不相等说明：这个元素在变成最终结果时需要移动，于是我们用l 记录下来，当然了，每次l++后判断是否到头了。

从右往左也是类似，如果不相等，说明对应元素最终也是需要挪动的。

---

第二种方法较难：

 我们从左到右找到非递减的右端点l，以及对应的r。

此时l~r之间的元素都是需要排序的，但是仅仅只是它们之间的元素吗？不是！l~r之间的元素可能有整个数组的最小值，那么按照惯例，它在排序后的数组中是要处于0号位置的。所以我们从l+1往右开始轮询，找到l左侧的子数组中，小于等于右侧子数组的最小值的最大值。从那个位置起（不包括它），可以把右侧最小元素搁置下。

同理，l~r之间存在整个数组最大值，这是要往右安置的，所有r指针需要往右移动，移动到某个位置------这个位置要能容纳地下这个比较大的元素。

和l r指针比较时，我们是仅仅需要找出l~r之间的最值元素呢？还是整个数组的？当然是整个数组的：

不难发现，l左侧这些元素可能大于r刚刚遍历走过的元素，如果要将整个数组排序，那么l左侧这些元素应该都要挪动。

所以：遍历时，应该让l--；然后新的指针从l+1开始，一直走到数组最右侧；

同理，r++；然后新的指针从r-1开始，一直走到0位置。 

最终返回值也值得一说：

我们最后两个for循环中的while循环：都是先--或者++之后再判断的，所以它们从while循环出来时，l r指向的都是与左侧或者右侧最值相等的值，相等的值不需要加入到答案中，比如13543，这五个元素，你要把3543重新排序结果是正确的，但是题目中要求最短，所以543才是最终答案。