Shortest Unsorted Continuous Subarray

Question

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.

Solution

用了一個比較複雜的方法解出來。這題有一個很厲害的解法，O(n)。有點類似兩個指針同時往左跟往右移動，如果 local max > nums[i], 代表不是 ascending，所以 end = i，如果 min < nums[i] 代表不是 descending, 所以 start = nums.length - 1 - i;

if (nums == null || nums.length == 0) {
        return 0;
    }

    int start = -1, end = -2, max = nums[0], min = nums[nums.length - 1];
    for (int i = 1; i < nums.length; i++) {
        max = Math.max(max, nums[i]);
        min = Math.min(min, nums[nums.length - 1 - i]);
        if (max > nums[i]) {
            end = i;
        }
        if (min < nums[nums.length - 1 - i]) {
            start = nums.length - 1 - i;
        }
    }
    return end - start + 1;