day29【LeetCode力扣】15.三数之和
1.题目描述
附上题目链接:15.三数之和
给你一个整数数组 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 。
2.题解
这道题是一道中等难度的题,不是很好去解决。使用两个嵌套的循环可以确定变量 a 和 b 的值,同时可以通过哈希方法检查 0-(a+b) 是否在给定数组中出现过。这种思路是正确的,但是题目中提到了一个难点,那就是不能有重复的三元组。
如果我们把所有满足条件的三元组加入到向量中,然后再进行去重处理,这将会非常耗时,通常会导致时间超限,这也是这个题目通过率低的原因之一。
去重操作处理起来较为复杂,有很多需要注意的小细节,在面试中很难一一考虑到。
尽管时间复杂度可以控制在 O(n^2),但由于难以进行有效的剪枝操作,所以整体上还是较为耗时。
大家可以尝试使用哈希方法来实现,亲自体验一下其难度。
c++
(1)排序+哈希
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i =0;i<nums.size();i++){
if(nums[i]>0){
break;
}
if(i>0&&nums[i] == nums[i-1]){
continue;
}
unordered_set<int> set;
for(int j=i+1;j<nums.size();j++){
if(j>i+2&&nums[j] ==nums[j-1]&&nums[j-1]==nums[j-2]){
continue;
}
int c=0-(nums[i]+nums[j]);
if(set.find(c)!=set.end()){
result.push_back({nums[i],nums[j],c});
set.erase(c);
}else{
set.insert(nums[j]);
}
}
}
return result;
}
};
解读:对输入向量进行排序。
遍历排序后的向量,对于每个元素 nums[i]:
如果 nums[i] 大于零,则终止循环,因为三数之和不可能大于零。
如果 i 不为零且 nums[i] 与 nums[i-1] 相等,则跳过当前元素,以避免重复解。
使用一个哈希集合 set 来存储剩余部分的元素,以便快速检查是否存在两个元素之和等于 nums[i] 的补数。
对于 i+1 到 nums.size() - 1 的每个元素 nums[j]:
如果 j 大于 i+2 且 nums[j] 与 nums[j-1] 以及 nums[j-2] 相等,则跳过当前元素,以避免重复解。
计算 nums[i] 和 nums[j] 的补数 c = -(nums[i] + nums[j])。
如果 c 在 set 中,则找到一个有效的三数之和,将其添加到结果向量中,并从 set 中删除 c,以避免重复添加相同的解。
如果 c 不在 set 中,则将 nums[j] 添加到 set 中。
最终,方法返回一个包含所有有效三数之和索引的向量。
(2)排序+双指针
实际上,对于这道题目而言,采用哈希方法并不是一个最佳选择,因为在去重过程中涉及到的细节较多,而在面试环境中很难立即编写出没有缺陷的代码。
当我们在两层循环中使用哈希方法时,能够进行的剪枝操作是非常有限的。尽管这样做可以将时间复杂度控制在 O(n^2),并且在某些情况下可以在 LeetCode 上成功通过,但程序的执行时间往往仍然较长。
这道题目使用双指针法 要比哈希法高效一些。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
//目的是找出nums[i]+nums[left]+nums[right]=0
for(int i=0;i<nums.size();i++){
if(nums[i]>0)
return res;
if(i>0&&nums[i]==nums[i-1])
continue;
int left = i+1;
int right = nums.size()-1;
while(right>left){
if(nums[i]+nums[left]+nums[right]>0) right--;
else if(nums[i]+nums[left]+nums[right]<0) left++;
else{
res.push_back(vector<int>{nums[i],nums[left],nums[right]});
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时,双指针同时收缩
right--;
left++;
}
}
}
return res;
}
};
代码的详细解释:
- 初始化:
res
:一个用于存储所有不重复的三元组的向量。sort(nums.begin(),nums.end());
:对数组nums
进行排序,以便于后续的双指针操作。- 外层循环:遍历数组
nums
的每一个元素。
if(nums[i]>0) return res;
:如果当前元素大于0,因为三数之和为0,所以后面的元素都不可能满足条件,直接返回结果。if(i>0&&nums[i]==nums[i-1]) continue;
:如果当前元素和前一个元素相同,跳过本次循环,避免出现重复的三元组。- 内层循环:使用双指针
left
和right
来找到和为0的三个数。
while(right>left)
:当左指针小于右指针时,进行循环。if(nums[i]+nums[left]+nums[right]>0) right--;
:如果三数之和大于0,说明右边的数太大,需要将右指针左移。else if(nums[i]+nums[left]+nums[right]<0) left++;
:如果三数之和小于0,说明左边的数太小,需要将左指针右移。else{
:如果三数之和等于0,找到了一个解。- 存储解:
res.push_back(vector<int>{nums[i],nums[left],nums[right]});
:将当前的三个数作为一个三元组加入到结果向量res
中。while (right > left && nums[right] == nums[right - 1]) right--;
:为了避免重复的三元组,当找到一个解后,右指针向左移动,直到指向一个不同的数。right--; left++;
:移动左右指针,寻找下一个可能的解。- 返回结果:
- 函数在所有可能的三元组都被检查后返回结果向量
res
。
这里涉及到几个去重逻辑的思考:
排序: 在开始之前,首先对数组
nums
进行排序。排序是为了使得在两端指针的移动过程中,数组中的元素能够按照大小顺序被访问,从而能够正确地通过比较来移动指针。外层循环去重:
if(i>0&&nums[i]==nums[i-1]) continue;
这个条件判断确保了当当前元素和前一个元素相同时,不进行内层循环的计算。这是因为在内层循环中,我们会尝试找到和为0的三元组,如果当前元素和前一个元素相同,那么它们组成的三元组在上一次内层循环中已经考虑过,因此这里直接跳过,避免重复计算。内层循环去重: 在找到一个有效的三元组之后,我们需要移动指针来寻找下一个可能的解。但是,我们需要避免因为数字重复而产生重复的三元组。因此,我们需要确保移动指针时不会回到之前的位置。
while (right > left && nums[right] == nums[right - 1]) right--;
这段代码确保了当右指针指向的元素和它前面的元素相同时,右指针继续左移,直到指向一个不同的元素。这样就避免了因为右指针的移动而重复计算相同的三元组。同样的逻辑应该应用于左指针,
while (left > 0 && nums[left] == nums[left - 1]) left--;
这段代码确保了当左指针指向的元素和它前面的元素相同时,左指针继续右移,直到指向一个不同的元素。
python
(1)双指针
实现逻辑和上面的c++是一样的,在这里就不多描述了。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if nums[i] > 0:
return res
if i>0 and nums[i]==nums[i-1]:
continue
left = i+1
right = len(nums)-1
while right>left:
sum_ = nums[i]+nums[left]+nums[right]
if sum_>0:
right -= 1
elif sum_<0:
left += 1
else:
res.append([nums[i],nums[left],nums[right]])
while right>left and nums[right]==nums[right-1]:
right -= 1
while right>left and nums[left]==nums[left+1]:
left += 1
right -= 1
left += 1
return res
(2)字典
<此解法来自“代码随想录”>
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
# 找出a + b + c = 0
# a = nums[i], b = nums[j], c = -(a + b)
for i in range(len(nums)):
# 排序之后如果第一个元素已经大于零,那么不可能凑成三元组
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]: #三元组元素a去重
continue
d = {}
for j in range(i + 1, len(nums)):
if j > i + 2 and nums[j] == nums[j-1] == nums[j-2]: # 三元组元素b去重
continue
c = 0 - (nums[i] + nums[j])
if c in d:
result.append([nums[i], nums[j], c])
d.pop(c) # 三元组元素c去重
else:
d[nums[j]] = j
return result
ok了,就到这里叭~~~
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
成功并不是最终目的,而是持续努力的结果。