【leetCode】第581题：最短无序连续子数组

川长思鸟来 2021-12-11 18:59 234阅读 0赞

**LeetCode 链接：[https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/][https_leetcode-cn.com_problems_shortest-unsorted-continuous-subarray]**

**题目：给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。**

> 示例 1:
> 
> 输入: \[2, 6, 4, 8, 10, 9, 15\]  
> 输出: 5  
> 解释: 你只需要对 \[6, 4, 8, 10, 9\] 进行升序排序，那么整个表都会变为升序排序。
> 
> 说明 :
> 
> 输入的数组长度范围在 \[1, 10,000\]。  
> 输入的数组可能包含重复元素 ，所以升序的意思是<=。

*  ### 双指针思路 ###

1、数组 temp 为 nums 复制而来，然后对 temp 从小到大进行排序；

2、然后利用双指针， 一个从头， 一个从尾， 向中间靠拢； 如果相等， 就 ++ 或者 --； 如果 left 和 right 指针指向的数值都不相等， 就 break；

3、需要排序的大小就为 \[left , right\] ，大小为：right - left + 1。

public class FindUnsortedSubarray_581 {
    
        public static int findUnsortedSubarray(int[] nums) {
            if(nums == null || nums.length < 1){
                return -1;
            }
    
            int[] temp = nums.clone();
            // 将temp数组从小到大排序
            Arrays.sort(temp);
            // 双指针：一个指向头，一个指向尾
            int left = 0;
            int right = nums.length - 1;
    
            while(left < right){
                boolean flag = true;
                // 找到不相等的位置后，对应的指针就停了，等另一个指针也不满足条件停下来时，就break了
                if(nums[left] == temp[left]){
                    left++;
                    flag = false;
                }
                if(nums[right] == temp[right]){
                    right--;
                    flag = false;
                }
                // 两个指针指向的位置都不相等时，flag才会为true，则 break
                if(flag == true){
                    break;
                }
            }
            return left >= right ? 0 : right - left + 1;
        }
    
        public static void main(String[] args) {
            int[] arr = {1, 3, 2, 2, 2};
            System.out.println(findUnsortedSubarray(arr));  // 4
        }
    }

*  感想：感觉这种题目，如果想到用双指针的话，还是很简单的，代码也很清晰。但是如果想不到双指针，使用暴力解的话，会出现很多边界分支情况。所以要掌握双指针这样的解题思路。

[https_leetcode-cn.com_problems_shortest-unsorted-continuous-subarray]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/