Day 2 - 数组进阶

📅 日期：2026年1月9日
🎯 主题：数组 + 双指针 + 排序

今日题目

题目1：三数之和 (3Sum)

难度：⭐⭐ 中等

链接：LeetCode 15. 三数之和

题目描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。

请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

输入：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
不同的三元组是 [-1,0,1] 和 [-1,-1,2]
注意，输出的顺序和三元组的顺序并不重要。

解题思路

排序 + 双指针法 ✅ 推荐

核心思想：

1. 排序：先对数组排序，方便去重和双指针操作
2. 固定第一个数：遍历数组，固定 nums[i] 作为第一个数
3. 双指针找两数之和：在 i+1 到 n-1 的范围内，使用双指针找 nums[j] + nums[k] = -nums[i]
4. 去重处理：
   • 如果 nums[i] == nums[i-1]，跳过（避免重复三元组）
   • 找到答案后，跳过所有相同的 nums[j] 和 nums[k]

关键点：

• 排序后，相同元素相邻，便于去重
• 双指针从两端向中间收缩，时间复杂度 O(n)
• 总时间复杂度：O(n²)

代码实现

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        
        // 排序
        Arrays.sort(nums);
        
        for (int i = 0; i < n - 2; i++) {
            // 跳过重复的第一个数
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // 如果最小的三个数之和都大于0，后面不可能有答案
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            
            // 如果当前数加上最大的两个数都小于0，跳过当前数
            if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {
                continue;
            }
            
            int left = i + 1, right = n - 1;
            int target = -nums[i];
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                
                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    
                    // 跳过重复的 left
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 跳过重复的 right
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
}

复杂度分析

• 时间复杂度：O(n²)，排序 O(n log n) + 双重循环 O(n²)
• 空间复杂度：O(1)，不考虑返回结果的空间

---

题目2：移动零 (Move Zeroes)

难度：⭐ 简单

链接：LeetCode 283. 移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

注意：必须在不复制数组的情况下原地对数组进行操作。

示例：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

输入: nums = [0]
输出: [0]

解题思路

方法一：双指针（快慢指针） ✅ 推荐

核心思想：

1. 使用两个指针：slow 指向下一个非零元素应该放置的位置，fast 用于遍历数组
2. fast 遍历数组，遇到非零元素就放到 slow 位置，然后 slow++
3. 遍历完成后，slow 之后的位置全部置为 0

方法二：一次遍历优化

更优雅的写法：

• 使用一个指针 j 记录非零元素应该放置的位置
• 遍历数组，遇到非零元素就与 j 位置交换，然后 j++
• 这样非零元素会自动交换到前面，零会被交换到后面

代码实现

方法一：双指针

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        
        // 将所有非零元素移到前面
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
        }
        
        // 将剩余位置置为0
        while (slow < nums.length) {
            nums[slow++] = 0;
        }
    }
}

方法二：一次遍历（交换）

class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // 交换非零元素到前面
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只使用常数额外空间

---

今日总结

学到了什么？

1. 排序 + 双指针：三数之和问题的经典解法，先排序再使用双指针
2. 去重技巧：在排序后的数组中，通过跳过相同元素来避免重复结果
3. 快慢指针：移动零问题展示了快慢指针的典型应用
4. 原地操作：在不使用额外空间的情况下重新排列数组

关键技巧

技巧	适用场景	时间复杂度
排序 + 双指针	多数和问题、有序数组	O(n²)
快慢指针	数组重排、去重	O(n)
剪枝优化	提前终止不必要的循环	减少实际运行时间

相似题目推荐

• 两数之和 II - 有序数组的两数之和
• 最接近的三数之和 - 三数之和的变种
• 四数之和 - 三数之和的扩展

明日计划

• Day 3 链表专题
• 练习：反转链表、合并两个有序链表