LeetCode 581. Shortest Unsorted Continuous Subarray

一、问题描述

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.

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

Example1

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.

二、题意分析

找到数组中乱序的子集（连续的），使得对该子集排序后整个数组有序，我们的任务就是找到满足条件的最小子集。

三、解题思路

首先将数组深度拷贝一份，然后排序，接着对比两个数组对应位置的元素，记录数组前，后第一次出现不一致的位置，它们之间的元素个数就是最短的。

代码实现

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if(nums.length == 1)
            return 0;
        // 深拷贝数组    
        int[] sortedArray = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedArray);
        int left = 0, right = nums.length - 1;
       // 找到前面开始出现不一致的初始位置
        while(left < right && nums[left] == sortedArray[left])
            left++;
        // 找到后面开始出现不一致的初始位置
        while(left < right && nums[right] == sortedArray[right])
            right--;
        // 数组正序
        if(left == right)
            return 0;
        return right - left + 1;
    }
}

时间、空间复杂度分析

1. 时间复杂度

O (nlogn)

2. 空间复杂度

O（n）