Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

描述

找到最短连续子数组，将这个子数组排序之后整个数组就有序了。输出最短连续子数组的长度。

分析

• 1:拿原数组与排序好的数组进行比较，找到第一个和最后一个不一致的位置j,j。返回值即为j-i+1.时间复杂度O(nlogn),空间复杂度O(n)
• 2:从1~N开始遍历，更新最大值max，并标记右侧一个小于max的数，其下标记为end
  从N->1开始遍历，更新最小值min，并标记左侧一个大于min的数，其下标为begin 返回end-begin+1。

Java：

 public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int n = nums.length;
            int maxNum = nums[0], minNum = nums[n - 1];
            int end = -2, begin = -1; 

            for (int i = 1; i < n; i++) {
                maxNum = Math.max(maxNum, nums[i]);
                if (maxNum > nums[i]) end = i;

                minNum = Math.min(minNum, nums[n - 1 - i]);
                if (minNum < nums[n - 1 - i]) begin = n - 1 - i;
            }
            return end - begin + 1;
        }
}

Swift：

class Solution {  
    func findUnsortedSubarray(_ nums: [Int]) -> Int {
        let n = nums.count
        var maxNum = nums[0]
        var minNum = nums[n-1]
        var end = -2
        var begin = -1
        for (i, item) in nums.enumerated() {
            maxNum = max(maxNum, item)
            if maxNum > nums[i]  {end = i}

            minNum = min(minNum, nums[n - 1 - i])
            if minNum < nums[n - 1 - i] {begin = n - 1 - i}
        }
        return end - begin + 1
    }
}

C：

int findUnsortedSubarray(int* nums, int numsSize) {  
    int i=0,j=numsSize-1, max=-2147483648, min=2147483647;

    while (i<numsSize && nums[i] <= nums[i+1])
        i++;
    while (j>=0 && nums[j] >= nums[j-1])
        j--;


    for (int k=i;k<=j;k++){
        if (nums[k]>max)
            max = nums[k];
        if (nums[k]<min)
            min = nums[k];
    }

    while (i>=0 && nums[i]>min)
        i--;
    while (j<numsSize && nums[j]<max)
        j++;


    if (j-i>0)
        return j-i-1;
    return 0;   
}

本题来自：leetcode

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/