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.

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:

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

 

先将原序列进行排序，然后跟原序列比较，看这个序列前后从哪个开始与排序好的序列开始不同，然后相减：

比如上面的例子中

2, 6, 4, 8, 10, 9, 15

排序以后

2,4,6,8,9,10,15

所以前面开始从4开始也就是第2位不同，后面开始10不同，也就是第6位，所以6-2+1=5

所以：

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        nums2=sorted(nums)
        right=0
        left=-1
        for index in range(0,len(nums)):
            if nums[index]!=nums2[index]:
                left=index
        for index in range(len(nums)-1,-1,-1):
            if nums[index]!=nums2[index]:
                right=index
        return left-right+1

之前因为不清楚sorted这个可以返回排序的序列的方法，所以用了两个深拷贝(copy.deepcopy)导致运行速度偏慢。