581. 最短无序连续子数组 (opens new window)

Description

Difficulty: 中等

Related Topics: 栈 (opens new window), 贪心 (opens new window), 数组 (opens new window), 双指针 (opens new window), 排序 (opens new window), 单调栈 (opens new window)

给你一个整数数组 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 <= 10⁴
• -10⁵ <= nums[i] <= 10⁵

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

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */

// Javascript 581. 最短无序连续子数组 排序
// 数组复制一份，从小到大排序，用两个指针分别从左右开始移动，如果原数组中的元素和排序后一致，就可以继续移动，否则退出。最后判断一下两个指针的位置就可以了。
/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    const copied = nums.slice(0).sort((a, b) => a - b)
    let i = 0
    let j = nums.length - 1
    while (copied[i] === nums[i] && i < nums.length) {
        i++
    }
    while (copied[j] === nums[j] && j >= 0) {
        j--
    }
    if (i >= j) {
        return 0
    }
    return j - i + 1
};