🔗 三数之和

题目来源：15. 三数之和 – 力扣（LeetCode）

---

📌 题目描述

给你一个整数数组 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]]
• 解释：
  • (-1) + 0 + 1 = 0 → [-1, 0, 1]
  • (-1) + (-1) + 2 = 0 → [-1, -1, 2]
    不同的三元组是 [-1,0,1] 和 [-1,-1,2]。输出顺序不限。

示例 2：

• 输入：nums = [0, 1, 1]
• 输出：[]
• 解释：无法找到三个数使其和为 0。

示例 3：

• 输入：nums = [0, 0, 0]
• 输出：[[0, 0, 0]]
• 解释：唯一满足条件的三元组是 [0, 0, 0]。

---

⚠️ 提示

• 3 <= nums.length <= 3000
• -10⁵ <= nums[i] <= 10⁵

---

💡 解法：排序 + 双指针（去重优化）—— O(n²) 时间

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 排序以便使用双指针和去重

        for (int i = 0; i < nums.length - 2; i++) {
            // 跳过重复的基准值（去重第一个数）
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 优化1：最小三数和 > 0，不可能找到解
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }

            // 优化2：当前值与最大两个数之和 < 0，说明太小了，继续增大 i
            if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < 0) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重：跳过相同的 left 和 right 值
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // 移动到下一个不同值的位置
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++; 
                } else {
                    right--; 
                }
            }
        }

        return result;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n²)
  • 排序：O(n log n)
  • 外层循环遍历 i：O(n)
  • 内层双指针遍历：O(n)
  • 总体：O(n²)，主导项为两层嵌套循环。
• 空间复杂度：O(1)
  • 不考虑返回结果所占用的空间，仅使用常数额外空间（i, left, right, sum 等变量）。
  • 若计入结果空间，则为 O(k)，其中 k 为满足条件的三元组数量。

---

🧩 解题思路

1. 排序预处理：
   先对数组排序，便于后续使用双指针，并支持去重判断。
2. 固定一个数，转化为两数之和问题：
   • 枚举第一个数 nums[i]，然后在 i+1 到 n-1 范围内寻找两个数，使其和为 -nums[i]。
   • 这就转化为经典的“两数之和”问题，可用双指针高效解决。
3. 双指针技巧：
   • left = i + 1，right = n - 1
   • 若三数之和 == 0：记录结果，并跳过重复值，双指针同时收缩。
   • 若和 < 0：说明左边太小，left++
   • 若和 > 0：说明右边太大，right--
4. 关键去重逻辑：
   • 外层 i 去重：if (i > 0 && nums[i] == nums[i-1]) continue;
   • 内层 left 和 right 去重：在找到解后，跳过相同值，避免重复三元组。
5. 剪枝优化：
   • 若当前 i 对应的最小三数和 > 0，则后续更大值不可能满足条件，直接 break。
   • 若当前 i 与最大两数之和 < 0，说明太小，continue 尝试下一个 i。