0%

Leetcode581

581. 最短无序连续子数组

难度中等609收藏分享切换为英文接收动态反馈

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

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

示例 1:

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

示例 2:

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

示例 3:

1
2
输入:nums = [1]
输出:0

提示:

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

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

Solution

目前想到的方法

  • 偏数学,找到最大最小值为界
  • 排序找差别,确定子数组两边下标
  • 排序后用二分(稍微提升)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @return {number}
*/
var findUnsortedSubarray = function (nums) {
let start, end = -1, point = 0;
let max = -100000, min = 10000;//题目给的大小区间
while (point < nums.length) {
// 找分界点
max > nums[point] ? end = point : max = nums[point]
min < nums[nums.length - point - 1] ? start = nums.length - point - 1 : min = nums[nums.length - point - 1]
point++;
}
return end === -1 ? 0 : end - start + 1;
};