问题抽象

找到数组连续的最小无序部分

算法：双指针

难点在于先想到暴力算法（排序比对），再想有没有更优的算法，能达到暴力算法相同的效果？

关键点在于想到排序后，我们只要找到左右两端正确放置元素的端点（有序边界），则边界的中间部分即为连续的最小无序部分

那么优化的思路也是这样，可以用双指针来做，找到原数组正确放置的元素的端点（不逆序的即为正确放置）

时间复杂度

$O(N)$

代码

class Solution {
public:

    // 难点：无法通过局部的逆序程度推出全局的逆序程度（2 3 1 1 1）
    // 关键点：先想到暴力解法，找到思路（最短长度就是中间那段），然后优化暴力解法
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r && nums[l] <= nums[l+1]){
            l ++;
        }
        if(l == r) return 0;
        while(l < r && nums[r] >= nums[r-1]){
            r --;
        }

        for(int i = l + 1; i < n; i ++)
            while(l >= 0 && nums[l] > nums[i]){
                l --;
            }

        for(int j = r - 1; j >= 0; j --)
            while(r < n && nums[r] < nums[j]) {
                r ++;
            }
        return r - l - 1;
    }
};