螺旋矩阵

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

▼
text
复制代码
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

代码

▼
java
复制代码
    class Solution {
    public List<Integer> 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<Integer> 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 的矩阵（奇数行和奇数列）：

▼
text
复制代码
[
  [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：

▼
text
复制代码
输入：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<List<Integer>> threeSum(int[] nums) {
        int n = nums.length; // 数组的长度
        Arrays.sort(nums); // 对数组进行排序，方便后续操作
        List<List<Integer>> ans = new ArrayList<>(); // 存储结果的列表
        List<Integer> 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; // 返回结果列表
    }
}