README.md

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) 的解决方案吗？

解法

方法一：排序

将排序后的数组与原数组进行比较，确定左右边界。

时间复杂度 $O(nlogn)$，其中 $n$ 表示 $nums$ 数组的长度。

更进一步优化，可以通过维护最大值和最小值，一次遍历得出结果（见 Golang 解法）

Python3

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

Java

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int left = 0, right = nums.length - 1;
        while (left <= right && nums[left] == arr[left]) {
            ++left;
        }
        while (left <= right && nums[right] == arr[right]) {
            --right;
        }
        return right - left + 1;
    }
}

C++

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> arr = nums;
        sort(arr.begin(), arr.end());
        int left = 0, right = arr.size() - 1;
        while (left <= right && nums[left] == arr[left]) ++left;
        while (left <= right && nums[right] == arr[right]) --right;
        return right - left + 1;
    }
};

Go

func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	arr := make([]int, n)
	copy(arr, nums)
	sort.Ints(arr)
	left, right := 0, n-1
	for left <= right && nums[left] == arr[left] {
		left++
	}
	for left <= right && nums[right] == arr[right] {
		right--
	}
	return right - left + 1
}

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
}

...