这是崔斯特的第一百零四篇原创文章

努力、奋斗

题目详述

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

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

示例 1:

1
2
3

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

说明 :

输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素，所以升序的意思是<=。

题目详解

方法一

将原数组拷贝一份，然后对拷贝后的数组进行排序。
对比原数组和排序后的数组，除去前面一部分和后面一部分相同的元素，剩余区间的长度就是结果。
时间复杂度为 O(nlogn)。

JAVA

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedNums);
        int i = 0;
        int j = sortedNums.length - 1;
        while (i <= j && nums[i] == sortedNums[i]) {
            ++i;
        }
        while (i <= j && nums[j] == sortedNums[j]) {
            --j;
        }
        return j - i + 1;
    }
    public static void main(String[] args) {
        int[] nums = new int[]{2, 6, 4, 8, 10, 9, 15};
        int i = new Solution().findUnsortedSubarray(nums);
        System.out.println(i);
    }
}

Go

package main
import (
   "fmt"
   "sort"
)
func findUnsortedSubarray(nums []int) int {
   sortedNum := make([]int, len(nums))
   copy(sortedNum, nums)
   sort.Ints(sortedNum)
   i, j := 0, len(nums)-1
   for i <= j && nums[i] == sortedNum[i] {
      i++
   }
   for i <= j && nums[j] == sortedNum[j] {
      j--
   }
   if i >= j {
      return 0
   }
   return j - i + 1
}
func main() {
   nums := []int{2, 1}
   n := findUnsortedSubarray(nums)
   fmt.Println(n)
}

Python

class Solution:
    def findUnsortedSubarray(self, nums):
        sortedarray = sorted(nums)
        i, j = 0, len(nums) - 1
        while i <= j and nums[i] == sortedarray[i]:
            i += 1
        while i <= j and nums[j] == sortedarray[j]:
            j -= 1
        return j - i + 1
if __name__ == '__main__':
    s = Solution().findUnsortedSubarray([2, 1])
    print(s)

方法二

遍历数组，同时进行从头到尾，从尾到头的遍历，分别找出无序连续子数组区间的右边和左边节点；
右边点，是从左到右不递增的点，
左边点，是从右到左不递减的点，
两点之间的距离就是所求值

JAVA

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int start = n - 1;
        int end = 0;
        int max = nums[0];
        int min = nums[n - 1];
        for (int i = 0; i < n; i++) {
            if (nums[i] >= max) {
                max = nums[i];
            } else {
                end = i;
            }
            if (nums[n - i - 1] <= min) {
                min = nums[n - i - 1];
            } else {
                start = n - i - 1;
            }
        }
        if (start >= end) {
            return 0;
        }
        return end - start + 1;
    }
    public static void main(String[] args) {
        int[] nums = new int[]{2, 6, 4, 8, 10, 9, 15};
        int i = new Solution().findUnsortedSubarray(nums);
        System.out.println(i);
    }
}

Go

package main
import "fmt"
func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	start, end := n-1, 0
	max, min := nums[0], nums[n-1]
	for i := 0; i < n; i++ {
		if nums[i] >= max {
			max = nums[i]
		} else {
			end = i
		}
		if nums[n-i-1] <= min {
			min = nums[n-i-1]
		} else {
			start = n - i - 1
		}
	}
	if start >= end {
		return 0
	}
	return end - start + 1
}
func main() {
	nums := []int{2, 1}
	n := findUnsortedSubarray(nums)
	fmt.Println(n)
}

Python

class Solution:
    def findUnsortedSubarray(self, nums):
        n = len(nums)
        start, end = 0, n - 1
        ma, mi = nums[start], nums[end]
        for i in range(n):
            if ma <= nums[i]:
                ma = nums[i]
            else:
                start = i
            if mi >= nums[n - i - 1]:
                mi = nums[n - i - 1]
            else:
                end = n - i - 1
        if start <= end:
            return 0
        return start - end + 1
if __name__ == '__main__':
    s = Solution().findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15])
    print(s)

等我提交之后，发现排在第一的解法比我快很多，我当时就呵呵呢

class Solution:
    def findUnsortedSubarray(self, nums):
        n = len(nums)
        max_num = nums[0]
        right = 0
        for i in range(n):
            if nums[i] >= max_num:
                max_num = nums[i]
            else:
                right = i
        left = n
        min_num = nums[-1]
        for i in range(n - 1, -1, -1):
            if nums[i] <= min_num:
                min_num = nums[i]
            else:
                left = i
        return right - left + 1 if right - left > 0 else 0