581_shortest_unsorted_continuous_subarray

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
}