# 螺旋矩阵给你一个 `m` 行 `n` 列的矩阵 `matrix` ，请按照 **顺时针螺旋顺序** ，返回矩阵中的所有元素。

``` 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5] ``` 代码 ```java class Solution { public List spiralOrder(int[][] matrix) { // 获取矩阵的行数和列数 int m = matrix.length, n = matrix[0].length; // 初始化边界：左边界 L，右边界 R，上边界 T，下边界 B int L = 0, R = n - 1, T = 0, B = m - 1; // 初始化索引：i 是列索引，j 是行索引 int i = -1, j = 0; // 存储结果的列表 List res = new ArrayList<>(); // 当左边界小于等于右边界，且上边界小于等于下边界时，继续螺旋遍历 while (L <= R && T <= B) { // 从左到右遍历上边界 while (++i <= R) { res.add(matrix[j][i]); // 将当前元素加入结果列表 } T++; // 上边界下移 i--; // 调整列索引，因为上面循环结束后 i 会超过右边界 R // 从上到下遍历右边界 while (++j <= B) { res.add(matrix[j][i]); // 将当前元素加入结果列表 } R--; // 右边界左移 j--; // 调整行索引，因为上面循环结束后 j 会超过下边界 B // 检查是否还有下边界需要遍历（避免重复遍历） if (T <= B) { // 从右到左遍历下边界 while (--i >= L ) { // 确保不会重复添加元素 res.add(matrix[j][i]); // 将当前元素加入结果列表 } B--; // 下边界上移 i++; // 调整列索引，因为上面循环结束后 i 会小于左边界 L } // 检查是否还有左边界需要遍历（避免重复遍历） if (L <= R) { // 从下到上遍历左边界 while (--j >= T) { // 确保不会重复添加元素 res.add(matrix[j][i]); // 将当前元素加入结果列表 } L++; // 左边界右移 j++; // 调整行索引，因为上面循环结束后 j 会小于上边界 T } } // 返回结果列表 return res; } } ``` ### 为什么需要 `if (T <= B)` 和 `if (L <= R)`？ #### 1. **奇数行或奇数列的情况**： - 当矩阵的行数或列数为奇数时，螺旋遍历到最后会剩下单独的一行或一列。 - 如果没有边界检查，代码可能会尝试重复遍历这一行或列。 #### 2. **边界收缩的顺序问题**： - 在每一轮螺旋遍历中，边界会逐渐收缩（`L++`, `R--`, `T++`, `B--`）。 - 如果在收缩边界后没有检查是否还有有效的行或列可以遍历，代码可能会尝试访问已经遍历过的区域。 ### 具体问题分析： #### 问题 1：奇数行或奇数列的情况假设有一个 **3x3 的矩阵**（奇数行和奇数列）： ``` [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] ``` - **没有边界检查的情况**： 1. **第一轮**： - 从左到右遍历上边界：`[1, 2, 3]`。 - 从上到下遍历右边界：`[6, 9]`。 - 从右到左遍历下边界：`[8, 7]`。 - 从下到上遍历左边界：`[4]`。 2. **第二轮**： - 此时边界已经收缩到中心元素 `5`。 - 如果没有边界检查，代码可能会尝试再次遍历已经遍历过的行或列，导致重复添加元素。 # 三数之和给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请你返回所有和为 `0` 且不重复的三元组。 **注意：**答案中不可以包含重复的三元组。 **示例 1：** ``` 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。 ``` 解题思路： 1. **排序**： - 对数组进行排序，使得相同的数相邻，方便后续去重和双指针操作。 2. **外层循环**： - 固定第一个数 `nums[i]`，并在循环中跳过重复的 `nums[i]`，避免重复的三元组。 3. **提前退出优化**： - 如果当前固定的数加上最小的两个数仍然大于 0，说明后面的数不可能满足条件，直接退出循环。 - 如果当前固定的数加上最大的两个数仍然小于 0，说明当前数太小，跳过本次循环。 4. **双指针法**： - 使用双指针 `j` 和 `k` 分别指向第二个数和第三个数。 - 根据三数之和与 0 的大小关系，移动指针 `j` 或 `k`。 5. **去重逻辑**： - 在找到满足条件的三元组后，跳过重复的 `nums[j]` 和 `nums[k]`，避免重复的三元组。 ### 时间复杂度： - 排序的时间复杂度为 **O(n log n)**。 - 外层循环遍历数组，内层循环使用双指针，总时间复杂度为 **O(n^2)**。 - 因此，总时间复杂度为 **O(n^2)**。 ### 空间复杂度： - 除了存储结果的列表外，只使用了常数级别的额外空间，因此空间复杂度为 **O(1)**（不考虑输出列表的空间）。解题代码 ```java class Solution { public List> threeSum(int[] nums) { int n = nums.length; // 数组的长度 Arrays.sort(nums); // 对数组进行排序，方便后续操作 List> ans = new ArrayList<>(); // 存储结果的列表 List list = null; // 用于临时存储每个三元组 // 外层循环，固定第一个数 nums[i] for (int i = 0; i < n - 2; i++) { int x = nums[i]; // 当前固定的第一个数 // 跳过重复的 nums[i]，避免重复的三元组 if (i > 0 && nums[i] == nums[i - 1]) { continue; } // 如果当前固定的数加上最小的两个数仍然大于 0，说明后面的数不可能满足条件，直接退出循环 if (x + nums[i + 1] + nums[i + 2] > 0) { break; } // 如果当前固定的数加上最大的两个数仍然小于 0，说明当前数太小，跳过本次循环 if (x + nums[n - 1] + nums[n - 2] < 0) { continue; } int j = i + 1; // 第二个数的指针，初始化为 i+1 int k = n - 1; // 第三个数的指针，初始化为数组末尾 // 内层循环，使用双指针法寻找满足条件的三元组 while (j < k) { int sum = x + nums[j] + nums[k]; // 计算三数之和 if (sum > 0) { k--; // 如果和大于 0，右指针左移，减小和 } else if (sum < 0) { j++; // 如果和小于 0，左指针右移，增大和 } else { // 找到满足条件的三元组 list = new ArrayList<>(); list.add(x); // 添加第一个数 list.add(nums[j]); // 添加第二个数 list.add(nums[k]); // 添加第三个数 ans.add(list); // 将三元组添加到结果列表 j++; // 移动左指针，跳过当前数 k--; // 移动右指针，跳过当前数 // 跳过重复的 nums[j]，避免重复的三元组 while (j < k && nums[j] == nums[j - 1]) { j++; } // 跳过重复的 nums[k]，避免重复的三元组 while (j < k && nums[k] == nums[k + 1]) { k--; } } } } return ans; // 返回结果列表 } } ```

LeetCode（54题和15题）的全部评论