581. 最短无序连续子数组

English Version

题目描述

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

 

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

 

提示：

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105

 

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

解法

将排序后的数组与原数组进行比较，确定左右边界。更进一步优化，可以通过维护最大值和最小值，一次遍历得出结果（见 Golang 解法）

Python3

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        numsSorted = sorted(nums)
        left, right = 0, n - 1
        while left < n and nums[left] == numsSorted[left]:
            left += 1
        while right >= 0 and nums[right] == numsSorted[right]:
            right -= 1
        return 0 if right == -1 else right - left + 1

Java

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] numsSorted = new int[n];
        System.arraycopy(nums, 0, numsSorted, 0, n);
        Arrays.sort(numsSorted);
        int left = 0, right = n - 1;
        while (left < n && nums[left] == numsSorted[left]) {
            left++;
        }
        while (right >= 0 && nums[right] == numsSorted[right]) {
            right--;
        }
        return right == -1 ? 0 : right - left + 1;
    }
}

Go

func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	maxn, minn := math.MinInt32, math.MaxInt32
	left, right := -1, -1
	for i := 0; i < n; i++ {
		if maxn > nums[i] {
			right = i
		} else {
			maxn = nums[i]
		}
		if minn < nums[n-i-1] {
			left = n - i - 1
		} else {
			minn = nums[n-i-1]
		}
	}
	if right == -1 {
		return 0
	}
	return right - left + 1
}

...