题目：最短无序连续子数组。
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。
package com.test.day6_9;
/**
* @author cosefy
* @date 2020/6/10
*/
public class FindUnsortedSubarray {
public static void main(String[] args) {
int[] nums = {2, 5, 2, 3};
int res1 = findUnsortedSubarray_Test1(nums);
int res3 = findUnsortedSubarray_Test3(nums);
System.out.println("The result of test1: " + res1);
System.out.println("The result of test3: " + res3);
}
解法一：暴力算法（不占用空间）
思路：一边从左边开始，依次确定当前元素是否是当前位置以后最小的元素，否则就退出循环，得到左边界；同理，获得右边界。
分析：时间复杂度（n），空间复杂度O（1）
易错点：注意参数的边界问题
思考：
-时间效率不高，可以考虑用空间换时间
public static int findUnsortedSubarray_Test1(int[] nums) {
int front_count = 0;
int rear_count = 0;
int i;
for (i = 0; i < nums.length; i++) {
boolean flag1 = true;
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j]) {
flag1 = false;
break;
}
}
if (flag1)
front_count++;
else
break;
}
for (int i2 = nums.length - 1; i2 >= i; i2--) {
boolean flag2 = true;
for (int j2 = i2 - 1; j2 >= i; j2--) {
if (nums[i2] < nums[j2]) {
flag2 = false;
break;
}
}
if (flag2)
rear_count++;
else
break;
}
return nums.length - front_count - rear_count;
}
解法二：先排序再确定边界
思路：排序之后，存放到一个新数组中，通过比较两个数组的差异得到左右边界。
分析：时间复杂度O（nlogn），空间复杂度O（n）
解法三：确定左右两边局部边界，再判断
思路：首先根据数组左边符合递增排序确定简单左边界，根据数组右边符合递增排序确定右边简单右边界。接下来，找出数组无序部分的最小值和最大值，对左右两个简单边界进行精确边界的判断。
分析：时间复杂度O（n），空间复杂度O（1）
易错点：注意循环的判断条件，注意取值
public static int findUnsortedSubarray_Test3(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
if (nums[left] < nums[left + 1]) //符合递增条件
++left; //简单左边界右移
else
break; //不满足条件则跳出循环
}
while (left < right) {
if (nums[right] > nums[right - 1])
--right;
else
break;
}
//上面两个循环得到左右两个初级边界
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i = left; i < right; i++) {
min = Math.min(min, nums[i]); //获得当前无序序列中的最小值
max = Math.max(max, nums[i]); //获得当前无序序列中的最大值
}
//下面根据min和max对初级边界进行精确缩减
for (int i = 0; i <= left; i++) {
if (nums[i] > min) {
left = i;
break;
}
}
for (int i = nums.length - 1; i >= right; i--) {
if (nums[i] < max) {
right = i;
break;
}
}
return right - left + 1;
}
}