LeetCode 581. 最短无序连续子数组

更多题解尽在 https://sugar.matrixlab.dev/algorithm 每日更新。
组队打卡，更多解法等你一起来参与哦！

LeetCode 581. 最短无序连续子数组，难度中等。

排序

解题思路：首先对数组排序，然后找出两侧顺序的数组，将不顺序的部分使用索引相减。

class Solution {public int findUnsortedSubarray(int[] nums) {int[] sortedNums = Arrays.stream(nums).sorted().toArray();int left, right;for (left = 0; left < nums.length; ++left) {if (sortedNums[left] != nums[left]) {break;}}if (left == nums.length) return 0;for (right = nums.length - 1; right >= 0; --right) {if (sortedNums[right] != nums[right]) {break;}}return right - left + 1;}
}

双指针

解题思路：

• 先找出左右两边的有序序列；
• 再找出 left 和 right 之间的最大最小值；
• 扩展边界
  • 从 left 向左扩展，直到找到一个不大于 min 的元素为止；
  • 从 right 向右扩展，直到找到一个不小于 max 的元素为止。

class Solution {public int findUnsortedSubarray(int[] nums) {int n = nums.length;int left = 0, right = n - 1;while (left < n - 1 && nums[left] <= nums[left + 1]) {left++;}while (right > 0 && nums[right] >= nums[right - 1]) {right--;}if (left >= right) return 0;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]);}while (left >= 0 && nums[left] > min) {left--;}while (right < n && nums[right] < max) {right++;}return right - left - 1;}
}