Leetcode.581 最短无序连续子数组

给你一个整数数组 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) 的解决方案吗？

常规思路
和排序后的数组进行比较即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func findUnsortedSubarray(nums []int) int {
	if sort.IntsAreSorted(nums) {
		return 0
	}
	numsSorted := append([]int{}, nums...)
	sort.Ints(numsSorted)
	left, right := 0, len(nums)-1
	for nums[left] == numsSorted[left] {
		left++
	}
	for nums[right] == numsSorted[right] {
		right--
	}
	return right - left + 1
}

一次遍历的话，先观察示例，从左往右看，数字应该是递增的，如果发现当前数字比前一个小，说明这个数字不符合条件，需要把边界更新到这里，同时更新已经遍历过的 max 数值，当某个 idx 之后，边界不再更新，根据我们设定的条件，这个 idx 右边的数应该都比 max 要大，这个 idx 比 max 要小，所以这个就是符合条件的右边界。同理，找到左边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func findUnsortedSubarray(nums []int) int {
	right, left := -1, -1
	// 注意 max 从 min起始；min 从 max 起始
	maxn, minn := math.MinInt64, math.MaxInt64
	n := len(nums)
	  
	for i:=0; i<n; i++ {
		if nums[i] < maxn {
			right = i
		} else {
			maxn = nums[i]
		}
		  
		// i 对位的位置
		if minn < nums[n-1-i] {
			left = n-1 - i
		} else {
			minn = nums[n-1-i]
		}
		}
		  
		// 本身有序
		if right == -1 {
		return 0
	}
	  
	return right - left + 1
}