LeetCode15

目录

• 题目描述
• 示例
• 思路分析
• 代码段
• 代码逐行讲解
• 复杂度分析
• 总结的知识点
• 整合
• 总结

---

题目描述

给你一个整数数组 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, -1, 2] 的和为 0。
• 三元组 [-1, 0, 1] 的和为 0。

---

示例 2

输入:

nums = [0, 1, 1]

输出:

[]

解释:

• 唯一可能的三元组 [0, 1, 1] 的和不为 0。

---

示例 3

输入:

nums = [0, 0, 0]

输出:

[[0, 0, 0]
]

解释:

• 唯一可能的三元组 [0, 0, 0] 的和为 0。

---

思路分析

问题核心

我们需要找到所有不重复的三元组，使得它们的和为 0。

思路拆解

1. 排序：
   • 将数组排序，方便后续的双指针操作。
2. 遍历数组：
   • 固定一个数 nums[i]，然后在剩余部分使用双指针寻找两个数 nums[left] 和 nums[right]，使得 nums[i] + nums[left] + nums[right] == 0。
3. 去重：
   • 如果 nums[i] 与前一个数相同，则跳过，避免重复。
   • 在找到满足条件的三元组后，跳过重复的 nums[left] 和 nums[right]。
4. 双指针：
   • 如果 sum > 0，则右指针左移。
   • 如果 sum < 0，则左指针右移。
   • 如果 sum == 0，则记录结果并移动指针。

---

代码段

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (nums[i] > 0) {return ans;}if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (right > left) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right--;} else if (sum < 0) {left++;} else {ans.add(Arrays.asList(nums[i], nums[left], nums[right]));while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;right--;left++;}}}return ans;}
}

---

代码逐行讲解

1. 排序数组：

   • 将数组排序，方便后续的双指针操作。

2. 初始化结果列表：

   • 用于存储所有满足条件的三元组。

3. 遍历数组：

   • 固定一个数 nums[i]，然后在剩余部分使用双指针寻找两个数 nums[left] 和 nums[right]。

4. 剪枝：

   • 如果当前数大于 0，则直接返回结果，因为后续的数都大于 0，无法满足和为 0。

5. 去重：

   • 如果当前数与前一个数相同，则跳过，避免重复。

6. 初始化双指针：

   • left 指向 i + 1，right 指向数组末尾。

7. 双指针遍历：

   • 当右指针大于左指针时，继续遍历。

8. 计算和：

   • 计算当前三元组的和。

9. 调整指针：

   • 如果 sum > 0，则右指针左移。
   • 如果 sum < 0，则左指针右移。
   • 如果 sum == 0，则记录结果并跳过重复的 nums[left] 和 nums[right]。

10. 返回结果：

    • 返回所有满足条件的三元组。

---

复杂度分析

时间复杂度

• 排序的时间复杂度为 O(n log n)。
• 双指针遍历的时间复杂度为 O(n^2)。
• 因此，总时间复杂度为 O(n^2)。

空间复杂度

• 排序的空间复杂度为 O(log n)。
• 结果列表的空间复杂度为 O(n^2)。

---

总结的知识点

1. 排序：

   • 使用 Arrays.sort 对数组进行排序。

2. 双指针：

   • 使用双指针在有序数组中寻找满足条件的两个数。

3. 去重：

   • 通过跳过重复的元素，避免生成重复的三元组。

4. 剪枝：

   • 通过提前终止循环，减少不必要的计算。

---

整合

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (nums[i] > 0) {return ans;}if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (right > left) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right--;} else if (sum < 0) {left++;} else {ans.add(Arrays.asList(nums[i], nums[left], nums[right]));while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;right--;left++;}}}return ans;}
}

---

总结

通过排序和双指针，能够高效地找到所有和为 0 的三元组。