三数之和
题目要求
给定一个整数数组 nums，要求找出所有不同的三元组 [nums[i], nums[j], nums[k]]，使得 i、j、k 互不相同，并且满足 nums[i] + nums[j] + nums[k] == 0。需要注意的是，返回的三元组列表中不能包含重复的三元组。
解题思路
解决这个问题的一个有效方法是使用排序加双指针的策略。以下是解题的步骤：
-
排序数组：首先对数组
nums进行排序。排序的目的是为了方便后续操作，可以使用双指针技术来避免重复的三元组，并且可以更快地跳过那些不可能组成和为 0 的三元组。 -
遍历数组：遍历排序后的数组，对于每个元素
nums[i]，设置两个指针，一个指向i+1（左指针），另一个指向数组的最后一个元素（右指针）。遍历的过程中，如果i大于 0 且nums[i]等于nums[i-1]，则跳过这个元素以避免重复的三元组。 -
双指针查找：在固定了
nums[i]之后，移动左右指针来寻找两个数，使得它们的和加上nums[i]等于 0。如果找到了这样的两个数，就将它们与nums[i]一起作为一个三元组添加到结果列表中。添加后，需要继续移动左右指针，并跳过所有重复的值，以防止添加重复的三元组。 -
左指针右移：如果当前的三个数的和小于 0，说明需要增加数值，因此将左指针向右移动。
-
右指针左移：如果当前的三个数的和大于 0，说明需要减少数值，因此将右指针向左移动。
-
重复上述步骤：重复步骤 3 到 5，直到左指针不再小于右指针。
-
返回结果：遍历完成后，返回存储三元组的结果列表。
通过以上步骤，可以确保找到所有不重复的三元组，且每个三元组的和为 0。
Golang 版本
package main
import (
"fmt"
"sort"
)
func threeSum(nums []int) [][]int {
sort.Ints(nums)
result := make([][]int, 0)
for i := 0; i < len(nums)-2; i++ {
// 跳过重复的数字
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, len(nums)-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
switch {
case sum < 0:
left++
case sum > 0:
right--
default:
result = append(result, []int{nums[i], nums[left], nums[right]})
// 跳过重复的数字
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
}
}
}
return result
}
func main() {
nums := []int{-1, 0, 1, 2, -1, -4}
result := threeSum(nums)
fmt.Println(result) // 输出找到的所有不重复的三元组
}
这段代码定义了一个 threeSum 函数，它接受一个整数切片 nums 作为输入，并返回一个二维切片，其中包含所有和为 0 的不重复三元组。主函数 main 提供了一个示例输入，并打印出 threeSum 函数的输出结果。
C++版本
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::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, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
++left;
} else if (sum > 0) {
--right;
} else {
result.push_back({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;
}
}
}
return result;
}
int main() {
std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
std::vector<std::vector<int>> result = threeSum(nums);
for (const auto& triplet : result) {
std::cout << '[';
for (int i = 0; i < triplet.size(); ++i) {
std::cout << triplet[i];
if (i < triplet.size() - 1) std::cout << ", ";
}
std::cout << ']' << std::endl;
}
return 0;
}
这段 C++代码定义了一个 threeSum 函数，它接受一个整数向量 nums 作为输入，并返回一个二维向量，其中包含所有和为 0 的不重复三元组。main 函数提供了一个示例输入，并打印出 threeSum 函数的输出结果。
Python 版本
def three_sum(nums):
nums.sort()
result = []
length = len(nums)
for i in range(length - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # Skip the duplicate numbers
left, right = i + 1, length - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1 # Skip the duplicate numbers
while left < right and nums[right] == nums[right - 1]:
right -= 1 # Skip the duplicate numbers
left += 1
right -= 1
return result
# Example usage:
nums = [-1, 0, 1, 2, -1, -4]
print(three_sum(nums))
这段 Python 代码定义了一个 three_sum 函数，它接受一个整数列表 nums 作为输入，并返回一个列表，其中包含所有和为 0 的不重复三元组。示例用法展示了如何调用这个函数并打印结果。
Java 版本
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // Skip duplicate elements
}
int left = i + 1, 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]));
while (left < right && nums[left] == nums[left + 1]) {
left++; // Skip duplicate elements
}
while (left < right && nums[right] == nums[right - 1]) {
right--; // Skip duplicate elements
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> result = solution.threeSum(nums);
for (List<Integer> triplet : result) {
System.out.println(triplet);
}
}
}
这段 Java 代码定义了一个 Solution 类，其中包含一个 threeSum 方法，它接受一个整数数组 nums 作为输入，并返回一个列表，其中包含所有和为 0 的不重复三元组。main 方法提供了一个示例输入，并打印出 threeSum 方法的输出结果。
Rust 版本
use std::collections::HashSet; fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut nums = nums; nums.sort_unstable(); let mut result = HashSet::new(); for i in 0..nums.len() { if i > 0 && nums[i] == nums[i - 1] { continue; // Skip the same result } let (mut start, mut end) = (i + 1, nums.len() - 1); while start < end { let sum = nums[i] + nums[start] + nums[end]; match sum.cmp(&0) { std::cmp::Ordering::Equal => { result.insert(vec![nums[i], nums[start], nums[end]]); start += 1; end -= 1; while start < end && nums[start] == nums[start - 1] { start += 1; // Skip the same number } while start < end && nums[end] == nums[end + 1] { end -= 1; // Skip the same number } } std::cmp::Ordering::Less => start += 1, std::cmp::Ordering::Greater => end -= 1, } } } result.into_iter().collect() } fn main() { let nums = vec![-1, 0, 1, 2, -1, -4]; let triplets = three_sum(nums); for triplet in triplets { println!("{:?}", triplet); } }
这段 Rust 代码定义了一个 three_sum 函数，它接受一个整数向量 nums 作为输入，并返回一个向量，其中包含所有和为 0 的不重复三元组。main 函数提供了一个示例输入，并打印出 three_sum 函数的输出结果。在这个实现中，使用了 HashSet 来自动去重复的三元组，最后将其转换为一个向量。
总结
上述 Rust 版本的解法采用了以下步骤来找出所有和为 0 的不重复三元组：
-
排序: 首先对输入的整数向量
nums进行排序。这是为了方便后续的双指针遍历，同时也使得相同的数字聚集在一起，便于跳过重复的三元组。 -
遍历: 使用外层循环遍历排序后的数组，从第一个元素开始，直到倒数第三个元素。这个元素将作为三元组中的第一个数字。
-
跳过重复的元素: 在外层循环中，如果当前元素与前一个元素相同，则跳过当前元素，以避免找到重复的三元组。
-
双指针查找: 对于每个外层循环选定的元素，使用两个指针（
start和end）在剩余数组中寻找两个数，使得这两个数与当前选定的元素之和为 0。start指针从当前元素的下一个元素开始，end指针从数组的最后一个元素开始向前移动。 -
三数之和判断: 如果三个数的和小于 0，则将
start指针向右移动；如果和大于 0，则将end指针向左移动；如果和等于 0，则将这三个数作为一个三元组添加到结果集中。 -
处理指针重复: 在找到一个有效的三元组后，需要移动
start和end指针，同时跳过所有重复的元素，以防止添加重复的三元组到结果集中。 -
结果去重: 使用
HashSet来存储三元组，这样可以自动去除重复的三元组。最后将HashSet转换为向量形式返回。 -
输出结果: 在
main函数中，调用three_sum函数并打印出返回的所有三元组。
这种解法的时间复杂度主要由排序和双指针遍历决定，排序的时间复杂度为 O(n log n)，双指针遍历的时间复杂度为 O(n^2)，因此总的时间复杂度为 O(n^2)。空间复杂度主要由结果集的存储决定，最坏情况下为 O(n^2)。