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;}
}