三数之和
给你一个整数数组 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]]
解释：
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] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
解法一：
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
if (!nums || nums.length < 3) {
return [];
}
let sums = [];
let sumsMap = [];
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
if ((nums[i] + nums[j] + nums[k]) === 0) {
let tmp = [
nums[i],
nums[j],
nums[k]
];
const tmpStr = tmp.sort((a, b) => { return a - b; }).join('');
if (sumsMap.indexOf(tmpStr) !== -1) {
continue;
}
sumsMap.push(tmpStr);
sums.push(tmp);
}
}
}
}
return sums;
};解法二：
要解决这个问题，我们需要找到一个整数数组 nums 中的所有不重复的三元组 [nums[i], nums[j], nums[k]]，使得它们的和为零。经典的方法是使用排序加上双指针来实现。下面是详细的解决方案及其实现。
算法步骤
排序数组：
首先对数组进行排序，这有助于使用双指针方法有效地找到合适的三元组。
遍历数组：
对于每个元素
nums[i]，在剩下的元素中使用双指针寻找另外两个元素nums[j]和nums[k]，使得nums[i] + nums[j] + nums[k] == 0。双指针查找：
如果和为 0，则找到一个三元组，存储结果，并移动两个指针以寻找其他可能的组合。
如果和小于 0，说明需要更大的数，因此移动
left指针以增加和。如果和大于 0，说明需要更小的数，因此移动
right指针以减小和。使用两个指针
left和right，分别指向i+1和数组的末尾。根据
nums[i] + nums[left] + nums[right]的和与 0 的关系调整指针：跳过重复元素：
为了避免重复的三元组结果，需要跳过数组中相邻的相同元素。即，当
nums[i] == nums[i-1]时，跳过该元素以避免重复计算。结果去重：
使用内置的数据结构来避免三元组重复，可以通过哈希集合或者简单地在算法中处理。
代码实现
def threeSum(nums):
# 对数组进行排序
nums.sort()
result = []
n = len(nums)
# 遍历数组，寻找三元组
for i in range(n - 2): # 如果当前数字与上一个数字相同，跳过以避免重复结果
if i > 0 and nums[i] == nums[i - 1]: continue
# 双指针初始化
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0: # 找到一个满足条件的三元组
result.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 total < 0: # 总和小于0，移动左指针
left += 1
else: # 总和大于0，移动右指针
right -= 1
return result
# 示例测试nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))
# 输出: [[-1, -1, 2], [-1, 0, 1]]复杂度分析
时间复杂度：O(n²)，其中 n 是数组的长度。排序的时间复杂度是 O(n log n)，而双指针查找的时间复杂度是 O(n²)。
空间复杂度：O(1)（不考虑存储结果的空间），因为我们只使用了常量级别的额外空间来处理指针。
说明
去重处理：通过跳过相同的元素，避免了重复的三元组。在
nums[i]的选择和left、right指针的移动中都进行了去重处理。边界条件：遍历数组时只到
n - 2，因为至少需要三个数来形成一个三元组。双指针策略：利用双指针从两端收缩，可以高效地找到满足条件的组合，避免了不必要的计算。
这种方法利用了排序和双指针的优势，使得我们能够在合理的时间复杂度下解决该问题。
