[刷题防痴呆] 0581 - 最短无序连续子数组 (Shorte

题目地址

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

题目描述

581. Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

 

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Example 2:

Input: nums = [1,2,3,4]
Output: 0
Example 3:

Input: nums = [1]
Output: 0

思路

• 先排序. 然后一一比较.
• O(n)的做法, 双指针. 分别找到left和right的位置.

关键点

代码

• 语言支持：Java

// 排序
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] copy = nums.clone();
        int left = 0;
        int right = -1;
        Arrays.sort(copy);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != copy[i]) {
                left = i;
                break;
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] != copy[i]) {
                right = i;
                break;
            }
        }

        if (right == -1) {
            return 0;
        }
        return right - left + 1;
    }
}

// 双指针
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int right = -1;
        int min = Integer.MAX_VALUE;
        int left = -1;

        for (int i = 0; i < nums.length; i++) {
            if (max > nums[i]) {
                right = i;
            } else {
                max = nums[i];
            }
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            if (min < nums[i]) {
                left = i;
            } else {
                min = nums[i];
            }
        }

        if (right == -1) {
            return 0;
        }
        return right - left + 1;
    }
}