581. 最短无序连续子数组（高频题）

581. 最短无序连续子数组

• 解题思路
• 代码

解题思路

数组问题一般就想到双指针。

• 将数组 nums 进行排序，记为 numsSort，然后比较 nums 和 numsSort 的元素来决定最左边和最右边不匹配的元素。它们之间的子数组就是要求的最短无序子数组。
• 首先，从左向右遍历两个数组，找到第一次两个数组中元素不同的位置，即为最左边的不同的位置也就是最短无序连续子数组的左边界。
• 然后，从右向左遍历两个数组，找到第一次两个数组中元素不同的位置，即为最右边的不同的位置也就是最短无序连续子数组的右边界。

实例：nums = [2,6,4,8,10,9,15]
将 nums 数组排序后为：[2,4,6,8,9,10,15]，当同时遍历两个数组时，不一样的元素的位置为 1 2 4 5(下标从 0 开始)，所以最短无序连续子数组的左边界为 1 右边界为 5。

代码

class Solution {
    public int findUnsortedSubarray(int[] nums) {

        int n = nums.length;
        if (n == 1) {
            return 0;
        }

        int[] numsSort = nums.clone();
        Arrays.sort(numsSort);
        int left = Integer.MAX_VALUE, right = 0;
        for (int i = 0; i < n; i++) {
            if (numsSort[i] != nums[i]) {
                left = i;
                break;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (numsSort[i] != nums[i]) {
                right = i;
                break;
            }
        }
        if (right - left >= 0) {
            return right - left + 1;
        } else {
            return 0;
        }
    }
}