class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
}
};
15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]
提示：
0 <= nums.length <= 3000-105 <= nums[i] <= 105原站题解
java 解法, 执行用时: 30 ms, 内存消耗: 50.6 MB, 提交时间: 2023-07-09 10:17:27
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}
python3 解法, 执行用时: 672 ms, 内存消耗: 17.9 MB, 提交时间: 2022-08-26 15:56:02
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 枚举 a
for first in range(n):
# 需要和上一次枚举的数不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 对应的指针初始指向数组的最右端
third = n - 1
target = -nums[first]
# 枚举 b
for second in range(first + 1, n):
# 需要和上一次枚举的数不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保证 b 的指针在 c 的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指针重合，随着 b 后续的增加
# 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans
golang 解法, 执行用时: 32 ms, 内存消耗: 7.3 MB, 提交时间: 2022-08-18 10:39:27
func threeSum(nums []int) [][]int {
n := len(nums)
sort.Ints(nums)
ans := make([][]int, 0)
// 枚举 a
for first := 0; first < n; first++ {
// 需要和上一次枚举的数不相同
if first > 0 && nums[first] == nums[first - 1] {
continue
}
// c 对应的指针初始指向数组的最右端
third := n - 1
target := -1 * nums[first]
// 枚举 b
for second := first + 1; second < n; second++ {
// 需要和上一次枚举的数不相同
if second > first + 1 && nums[second] == nums[second - 1] {
continue
}
// 需要保证 b 的指针在 c 的指针的左侧
for second < third && nums[second] + nums[third] > target {
third--
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third {
break
}
if nums[second] + nums[third] == target {
ans = append(ans, []int{nums[first], nums[second], nums[third]})
}
}
}
return ans
}