【面试高频题】难度 1/5，简单双指针运用

宫水三叶的刷题日记

发布于 2023-09-07 09:52:48

2300

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

题目描述

这是 LeetCode 上的 「581. 最短无序连续子数组」 ，难度为 「中等」。

Tag : 「排序」、「双指针」

给你一个整数数组 nums ，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]

输出：5

解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]

输出：0

示例 3：

输入：nums = [1]

输出：0

提示：

进阶：你可以设计一个时间复杂度为的解决方案吗？

双指针 + 排序

最终目的是让整个数组有序，那么我们可以先将数组拷贝一份进行排序，然后使用两个指针和分别找到左右两端第一个不同的地方，那么这一区间即是答案。

代码：

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) i++;
        while (i <= j && nums[j] == arr[j]) j--;
        return j - i + 1;
    }
}

时间复杂度：
空间复杂度：

双指针 + 线性扫描

另外一个做法是，我们把整个数组分成三段处理。

起始时，先通过双指针和找到左右两次侧满足 「单调递增」 的分割点。

即此时和满足升序要求，而中间部分 「不确保有序」。

然后我们对中间部分进行遍历：

发现：由于对部分进行排序后会出现在后，将不满足整体升序，此时我们需要调整分割点的位置；
发现：由于对部分进行排序后会出现在前，将不满足整体升序，此时我们需要调整分割点的位置。

❝一些细节：在调整和的时候，我们可能会到达数组边缘，这时候可以建立两个哨兵：数组左边存在一个足够小的数，数组右边存在一个足够大的数。 ❞

代码：

class Solution {
    int MIN = -100005, MAX = 100005;
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) i++;
        while (i < j && nums[j] >= nums[j - 1]) j--;
        int l = i, r = j;
        int min = nums[i], max = nums[j];
        for (int u = l; u <= r; u++) {
            if (nums[u] < min) {
                while (i >= 0 && nums[i] > nums[u]) i--;
                min = i >= 0 ? nums[i] : MIN;
            }
            if (nums[u] > max) {
                while (j < n && nums[j] < nums[u]) j++;
                max = j < n ? nums[j] : MAX;
            }
        }
        return j == i ? 0 : (j - 1) - (i + 1) + 1;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-08-18，如有侵权请联系 cloudcommunity@tencent.com 删除

int