题目描述

Shortest Unsorted Continuous Subarray

给定一个无序数字数组，需要找出一个连续的子数组，满足只要该字数组重新按升序排列，则整个数组满足升序。找到这样的子数组，返回它的长度。 如不存在这样的子数组，返回 0
示例1：

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: 只要 [6, 4, 8, 10, 9] 为升序排列，则整个数组转化为升序

另：

• 输入数组长度范围为 [1, 10,000].
• 输入数组可以还有重复值，所以升序中会含有相等的情况.

From leetcode No.581 Easy (opens new window)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    
};

解法

点击查看

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function (nums) {
  const len = nums.length
  let i = 0
  let j = len - 1
  const n = Array.from(nums).sort((a, b)=>a-b)
  while(j > 0){
    if(n[j] === nums[j]){
      j--;
      continue;
    }
    break;
  }
  if(j === 0)
    return 0
  while (i < j) {
    if(n[i] === nums[i]){
      i++;
      continue;
    }
    break;
  }
  return j - i + 1
};

总结

思路是将数组按升序排序后生成新的数组，然后比较数组两端的元素。
获取到起始不相等的元素索引 i 以及末尾不相等元素索引 j，即索引 i - j的元素需要重新排序。
特殊情况是 i===j===0, 即数组本身是有序的，故不存在这样的子序列，返回 0。
这里避免理解歧义，数组本身也是自身的子序列。

学习提交的最快解法，思路差不多，找不相等的序列的起始索引和终点索引，但方法不同，没有排序，也没有使用新数组，更加巧妙。
思路如下：

• 从前到后循环遍历，寻找乱序的起点位置
  • 即找到第一个比前一个元素值小的元素，如果不存在说明没有乱序
• 如果存在乱序，再从后向前循环遍历，寻找乱序的终点位置。
  • 同理，找到第一个比前一个元素值大的元素
• 以上前后遍历顺序可调换，一次遍历如果不存在乱序则直接返回 0

点击查看

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function (nums) {
  let start, min = nums[nums.length - 1];
  for (let i = nums.length - 2; i >= 0; i--) {
    min = Math.min(min, nums[i])
    if (nums[i] != min) {
      start = i
    }
  }
  if (start === undefined)
      return 0
  let end, max = nums[0];
  for (let i = 1; i < nums.length; i++) {
    max = Math.max(max, nums[i])
    if (nums[i] != max) {
      end = i
    }
  }
  return end - start + 1
};