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 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例二：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例三：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
【算法设计思想】
1. 数组排序
• 对输入数组 nums 进行从小到大的排序。排序后，便于使用双指针技术来查找符合条件的三元组。
2. 遍历数组
• 从数组的第一个元素开始，依次遍历每个元素 nums[i]。对于每个元素，目标是找到两个其他元素，使得这三个数的和为零。
3. 跳过重复元素
• 如果当前元素 nums[i] 与前一个元素相同（即 nums[i] == nums[i - 1]），则跳过该元素，以避免产生重复的三元组。
4. 初始化双指针
• 设置两个指针：left 指向 i 后面的第一个元素（i + 1），right 指向数组的末尾（n - 1）。
5. 双指针查找
• 计算当前三元组的和 sum = nums[i] + nums[left] + nums[right]。
• 如果 sum == 0，说明找到了符合条件的三元组，将其添加到结果集 ans 中。
• 然后移动 left 和 right 指针，跳过重复的元素，以避免重复的三元组。
• 如果 sum < 0，说明当前和太小，增大 left 指针的值，即 left++。
• 如果 sum > 0，说明当前和太大，减小 right 指针的值，即 right--。
6. 继续查找
• 重复第 5 步，直到 left 和 right 指针相遇，结束对当前元素 nums[i] 的查找。
7. 返回结果
• 遍历完所有元素后，返回保存所有符合条件三元组的结果集 ans。
【算法描述】
// 寻找数组中所有不重复的三元组，这些三元组的和为零
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> ans;
// 对数组进行排序，以便后续操作
sort(nums.begin(), nums.end());
// 遍历数组，尝试为每个元素找到所有可能的两数组合，使其和为零
for (int i = 0; i < nums.size(); i++)
{
// 跳过重复的元素，避免重复的三元组
if (i > 0 && nums[i] == nums[i - 1])
continue;
// 初始化左右指针
int left = i + 1;
int right = nums.size() - 1;
// 设置目标值，即当前元素的相反数，用于后续的两数之和的判断
int target = 0 - nums[i];
// 当左指针小于右指针时，执行循环
while (left < right)
{
// 判断当前左右指针所指的数之和是否等于目标值
if (target == nums[left] + nums[right])
{
// 找到符合条件的三元组，将其添加到结果中
ans.push_back({nums[i], nums[left], nums[right]});
// 移动左指针，跳过重复的元素
while (left < right && nums[left] == nums[left + 1])
left++;
// 移动右指针，跳过重复的元素
while (left < right && nums[right] == nums[right - 1])
right--;
// 同时移动左右指针，继续寻找下一组符合条件的数
left++;
right--;
}
else if (target > nums[left] + nums[right])
{
// 如果和小于目标值，移动左指针，增大和的值
left++;
}
else
{
// 如果和大于目标值，移动右指针，减小和的值
right--;
}
}
}
// 返回所有找到的三元组
return ans;
}
Python:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 获取列表中元素的数量
n = len(nums)
# 对列表进行排序，以便更容易避免重复元素并使用双指针技巧
nums.sort()
# 初始化一个空列表来存储结果
ans: List[List[int]] = []
# 遍历列表
for i in range(n):
# 跳过重复的元素，以避免重复的三元组
if i > 0 and nums[i] == nums[i - 1]:
continue
# 初始化两个指针
left = i + 1
right = n - 1
# 使用双指针技巧找到和为 -nums[i] 的一对元素
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if current_sum == 0:
# 如果和为零，将三元组添加到结果列表中
ans.append([nums[i], nums[left], nums[right]])
# 跳过左指针的重复元素
while left < right and nums[left] == nums[left + 1]:
left += 1
# 跳过右指针的重复元素
while left < right and nums[right] == nums[right - 1]:
right -= 1
# 移动两个指针
left += 1
right -= 1
elif current_sum < 0:
# 如果和小于零，将左指针向右移动以增加和
left += 1
else:
# 如果和大于零，将右指针向左移动以减少和
right -= 1
# 返回三元组列表
return ans
Java：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
// 排序数组，以便使用双指针技术
Arrays.sort(nums);
for (int i = 0; i < n; i++) {
// 跳过重复元素
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
// 找到一个三元组，添加到结果列表
ans.add(Arrays.asList(nums[i], nums[left], nums[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 ans;
}
}