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

代码参考:

package main

import (
    "fmt"
    "sort"
)

func main() {
    fmt.Println(findUnsortedSubarray([]int{2, 6, 4, 8, 10, 9, 15}))
    fmt.Println(findUnsortedSubarray([]int{2, 1}))
}

// 先排序,再双指针 ok
func findUnsortedSubarray(nums []int) int {
    backup := make([]int, len(nums))
    copy(backup, nums)

    sort.Ints(nums)
    start, end := -1, -1
    for i, num := range backup {
        if nums[i] != num {
            start = i
            break
        }
    }
    if start == -1 {
        return 0
    }

    for i := len(backup) - 1; i >= 0; i-- {
        if nums[i] != backup[i] {
            end = i
            break
        }
    }

    return end - start + 1
}
最后编辑: kuteng  文档更新时间: 2021-06-05 10:16   作者:kuteng