最短无序连续子数组

1. 题目描述

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

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

2. 思路

1. 思路一
   • 排序
   • 相对所有元素排序
   • 然后对比原数组，从左往右找到第一个不同的元素，从右往左找到第一个不同的元素
   • 两者相减即可得出答案

3. 实现

3.1. 排序

func findUnsortedSubarray(nums []int) int {
    dst := make([]int, len(nums))
    copy(dst, nums)
    mergeSort(dst,0,len(dst)-1)
    

    left := 0
    for i := 0; i < len(nums); i++ {
        if dst[i] != nums[i] {
            left = i
            break
        }
    }

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

    if left == 0 && right == 0 {
        return 0
    }

    return right-left+1
}

func mergeSort(nums []int, left, right int) {
    if left >= right {
        return
    }

    mid := left+(right-left)>>1
    mergeSort(nums, left, mid)
    mergeSort(nums, mid+1, right)
    
    merge(nums, left, mid, right)
}

func merge(nums []int, left, mid, right int) {
    i, j, k := left, mid+1, 0
    tmp := make([]int, right-left+1)
    for i <= mid && j <= right {
        if nums[i] < nums[j] {
            tmp[k] = nums[i]
            i++
        }else {
            tmp[k] = nums[j]
            j++
        }
        k++
    }

    for i <= mid {
        tmp[k] = nums[i]
        i++
        k++
    }

    for j <= right {
        tmp[k] = nums[j]
        j++
        k++
    }

    for i:=0; i<len(tmp); i++{
        nums[left+i] = tmp[i]
    }
}

4. 参考

• 找左右边界（类似快排算法的思路 - 最短无序连续子数组 - 力扣（LeetCode）