题目地址
https://leetcode-cn.com/problems/3sum/
思路
哈希解法
去重的过程不好处理,有很多小细节,如果在面试中很难想到位
时间复杂度:O(n^2),但是运行时间很长,不好做剪枝操作
双指针
推荐使用这个方法,排序后用双指针前后操作,比较容易达到去重的目的,但也有一些细节需要注意,我在如下代码详细注释了需要注意的点
时间复杂度:O(n^2)
哈希法代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); // 找出a + b + c = 0 // a = nums[i], b = nums[j], c = -(a + b) for (int i = 0; i < nums.size(); i++) { // 排序之后如果第一个元素已经大于零,那么不可能凑成三元组 if (nums[i] > 0) { continue; } if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重 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]) { // 三元组元素b去重 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);// 三元组元素c去重 } else { set.insert(nums[j]); } } } return result; } };
双指针法代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47class 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) { return result; } // 错误去重方法,将会漏掉-1,-1,2 这种情况 /* if (nums[i] == nums[i + 1]) { continue; } */ // 正确去重方法 if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.size() - 1; while (right > left) { // 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组 /* while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; */ if (nums[i] + nums[left] + nums[right] > 0) { right--; } else if (nums[i] + nums[left] + nums[right] < 0) { left++; } else { result.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 result; } };
更多精彩文章持续更新,可以微信搜索「 代码随想录」第一时间阅读,关注后有大量的学习资料和简历模板可以免费领取,本文 GitHub:https://github.com/youngyangyang04/leetcode-master 已经收录,欢迎star,fork,共同学习,一起进步。
最后
以上就是虚幻未来最近收集整理的关于「leetcode」C++题解:15.三数之和 /3Sum 方法1:哈希法,方法2:排序+双指针,详细注释的全部内容,更多相关「leetcode」C++题解:15.三数之和内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复