LeetCode题练习与总结：最短无序连续子数组--581

一、题目描述

给你一个整数数组 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

提示：

• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5

二、解题思路

1. 首先复制原数组，并对复制后的数组进行排序。
2. 然后分别从数组的两端开始比较原数组与排序后的数组。
3. 找到第一个不同的元素位置，即为需要排序的子数组的起始位置。
4. 找到最后一个不同的元素位置，即为需要排序的子数组的结束位置。
5. 计算这两个位置之间的距离，即为需要排序的最短子数组的长度。

三、具体代码

import java.util.Arrays;class Solution {public int findUnsortedSubarray(int[] nums) {// 复制原数组并进行排序int[] sortedNums = nums.clone();Arrays.sort(sortedNums);// 初始化子数组的起始和结束位置int start = 0, end = nums.length - 1;// 从两端开始比较原数组与排序后的数组while (start < nums.length && nums[start] == sortedNums[start]) {start++;}while (end > start && nums[end] == sortedNums[end]) {end--;}// 计算需要排序的子数组的长度return end - start + 1;}
}

这段代码首先复制了原数组并进行排序，然后从数组的两端开始比较，直到找到第一个和最后一个不同的元素，最后计算这两个位置之间的距离，即为需要排序的最短子数组的长度。如果整个数组已经是有序的，那么返回的长度将是0。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 复制原数组：这个操作的时间复杂度是 O(n)，其中 n 是数组的长度。
• 对数组进行排序：使用的是 Arrays.sort() 方法，该方法在大多数情况下使用的是双轴快速排序，其平均时间复杂度是 O(n log n)。
• 比较原数组与排序后的数组：最坏情况下需要遍历整个数组，因此时间复杂度是 O(n)。

综上所述，总的时间复杂度是 O(n) + O(n log n) + O(n)，简化后是 O(n log n)，因为排序操作通常是最大的时间开销。

2. 空间复杂度

• 复制原数组：这个操作的空间复杂度是 O(n)，因为需要额外的空间来存储一个与原数组大小相同的数组。

因此，总的空间复杂度是 O(n)。

五、总结知识点

• 数组操作：

  • 使用 clone() 方法来复制一个数组。这是一个浅拷贝，适用于基本数据类型。
  • 使用 Arrays.sort() 方法对数组进行排序。这个方法内部使用的是双轴快速排序算法。

• 循环结构：

  • 使用 while 循环来遍历数组元素，以找到需要排序的子数组的起始和结束位置。

• 数组索引与边界条件：

  • 使用数组索引来访问数组元素。
  • 使用边界条件来防止数组越界。例如，start < nums.length 和 end > start。

• 逻辑判断：

  • 使用 == 运算符来比较数组元素是否相等。
  • 使用 && 运算符来进行逻辑与运算，确保在满足特定条件时才执行循环体中的代码。

• 算法逻辑：

  • 通过比较原数组与排序后的数组，确定需要排序的子数组的边界。
  • 计算子数组长度的逻辑：end - start + 1。

• 方法定义与返回值：

  • 定义了一个 findUnsortedSubarray 方法，它接受一个整数数组作为参数，并返回一个整数，表示需要排序的子数组的长度。

• Java基础语法：

  • 类定义（class 关键字）。
  • 方法定义（public 访问修饰符，返回类型，方法名，参数列表）。
  • 变量声明与初始化（int start = 0, end = nums.length - 1;）。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。