581-最短无序连续子数组
访问量:35

一、题目

题目地址:https://leetcode.com/problems/shortest-unsorted-continuous-subarray/


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

你找到的子数组应是最短的,请输出它的长度。


示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]

输出: 5

解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。


说明 :

输入的数组长度范围在 [1, 10,000]。

输入的数组可能包含重复元素 ,所以升序的意思是<=。


二、解法

1、解法一

func findUnsortedSubarray(nums []int) int {
	numsLen := len(nums)
	if numsLen == 0 {
		return 0
	}


	var startId int = 0
	var endId int = numsLen - 1
	var isBreak bool = false

	for i := 0; i < numsLen; i++ {
		for j := i + 1; j <= endId; j++ {
			if nums[i] > nums[j] {
				isBreak = true
				break
			}
		}
		startId = i
		if isBreak {
			break
		}
	}

	if startId == numsLen - 1 {
		return 0
	}

	isBreak = false
	for k :=numsLen - 1; k >= startId; k--  {
		for j := k - 1; j >= startId; j-- {
			if nums[k] < nums[j] {
				isBreak = true
				break
			}
		}
		endId = k
		if isBreak {
			break
		}
	}

	return endId - startId + 1
}