Leetcode 581.最短无序连续子数组（Shortest Unsorted Continuous Subarray）

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

1 题目描述（Leetcode题目链接）

??给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。

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

说明 :

• 输入的数组长度范围在 [1, 10,000]。
• 输入的数组可能包含重复元素 ，所以升序的意思是<=。

2 题解

??最容易想到的方法大概就是排序了，排好序后能很清楚地看清中间的哪一部分子数组发生了改变。

class Solution:def findUnsortedSubarray(self, nums: List[int]) -> int:length = len(nums)new_nums = sorted(nums)i, j = 0, length - 1while i <= j:if nums[i] == new_nums[i]:i += 1elif nums[j] == new_nums[j]:j -= 1else:breakreturn j - i + 1

??如果思考线性时间复杂度的方法，就要找特征，无序子数组中最小元素的正确位置可以决定左边界，最大元素的正确位置可以决定右边界。

• 从头开始遍历数组，一旦遇到降序的元素，记录最小元素为 $min$;
• 从头开始遍历数组，遇到第一个比 $min$大的就是左边界；
• 逆序遍历数组，当数组出现升序的时候，记录最大元素为 $max$;
• 逆序遍历数组，遇到第一个比 $max$小的就是右边界。

官方题解如下

public class Solution {public int findUnsortedSubarray(int[] nums) {int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;boolean flag = false;for (int i = 1; i < nums.length; i++) {if (nums[i] < nums[i - 1])flag = true;if (flag)min = Math.min(min, nums[i]);}flag = false;for (int i = nums.length - 2; i >= 0; i--) {if (nums[i] > nums[i + 1])flag = true;if (flag)max = Math.max(max, nums[i]);}int l, r;for (l = 0; l < nums.length; l++) {if (min < nums[l])break;}for (r = nums.length - 1; r >= 0; r--) {if (max > nums[r])break;}return r - l < 0 ? 0 : r - l + 1;}
}