三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
Python3实现
借助两数之和
# @author:leacoder
# @des: 借助两数之和 三数之和
class Solution(object):
def threeSum(self, nums):
nums.sort() #排序 方便去重
res = []
for i, num in enumerate(nums): #一层循环
if i > 0 and nums[i] == nums[i-1]: # 避免重复
continue
new_nums = nums[i+1:] #剔除 一层循环后的数
two_sums = self.twoSum(new_nums, -num) #由于何为0 两数之和要为 -num
for two_sum in two_sums:
res.append([num, new_nums[two_sum[0]], new_nums[two_sum[1]]])
return res
def twoSum(self, nums, target):
d = {}
res = []
hit = False
for i, num in enumerate(nums):
if i > 1 and nums[i] == nums[i-1] and hit:
continue
if num in d:
res.append([d[num], i])
hit = True
else:
d[target - num] = i
hit = False
return res
一层枚举 左右两指针形式
# @author:leacoder
# @des: 一层枚举 左右两指针形式 三数之和
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for index1,value in enumerate(nums[:-2]): #一层循环
if index1>0 and nums[index1] == nums[index1-1]: #不可以包含重复的三元组
continue
left,right = index1+1,len(nums)-1 #左右指针形式 左：一层数据右侧开始 右:数据最右端开始
while left<right: #循环条件 依据实际大小情况，选择左或右指针向中间移动 但右必定大于左
sumtmp = nums[index1] + nums[left] + nums[right] #三数和
if sumtmp <0: left +=1 # <0 表明和小了，那么左指针向右+1 真大 nums[left] nums已经排序 右边必定大于 左边
elif sumtmp >0: right -=1 #同上
else: #刚好为0
res.append((nums[index1],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
return res
C++实现
一层枚举 左右两指针形式
/*
*@author:leacoder
*@des: 一层枚举 左右两指针形式 三数之和
*/
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res; //返回值
if(nums.size()<3){ //输入检查
return res;
}
sort(nums.begin(), nums.end()); //排序
for (int i = 0; i < nums.size()-2; i++) //一层循环
{
if(i>0 && nums[i] == nums[i-1])
continue;
int target = -nums[i]; //其他两数和
int l = i + 1, r = nums.size() - 1; //左右指针形式 l 左 r右
while (l < r)
{
if (nums[l] + nums[r] < target) //小于目标 l 增加
++l;
else if (nums[l] + nums[r] > target) //大于目标 r 减少
--r;
else{ //刚好
res.push_back(vector<int>{nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l+1])
l++;
while (l < r && nums[r] == nums[r-1])
r--;
l++; r--;
}
}
}
return res;
}
};
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习