15. 3Sum
15
2023-09-11 14:22:48 时间
Given an array nums
of n integers, are there elements a, b, c in nums
such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
AC code:
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int len = nums.size(); vector<vector<int> > v; sort(nums.begin(), nums.end()); int front, tear, target, sum; for (int i = 0; i < len; ++i) { target = -nums[i]; front = i + 1; tear = len-1; while (front < tear) { sum = nums[front] + nums[tear]; if (sum < target) { front++; } else if (sum > target) { tear--; } else { vector<int> sub_ans(3, 0); sub_ans[0] = nums[i]; sub_ans[1] = nums[front]; sub_ans[2] = nums[tear]; v.push_back(sub_ans); while (front < tear && nums[front] == sub_ans[1]) front++; while (front < tear && nums[tear] == sub_ans[2]) tear--; } } while ((i+1) < len && nums[i] == nums[i+1]) { i++; } } return v; } };
Runtime: 120 ms, faster than 40.59% of C++ online submissions for 3Sum.
相关文章
- 安卓逆向_15( 一 ) --- JNI 和 NDK
- Refactor this method to reduce its Cognitive Complexity from 18 to the 15 allowed.
- Word控件Spire.Doc 【文本】教程(15) ;如何在 C#、VB.NET 的组合框中添加、选择和删除项目
- 【PAT乙级】1011 A+B 和 C (15 分)
- 每日一练增设排行榜、CODECHINA支持Jupyter Notebook使用啦【第15期*2021.10.11】
- 2018年9月15日上海MVP线下技术交流活动简报
- 2014第15周五
- SwiftUI CloudKit 入门之 15 根据用户的要求限制访问或从用户数据中删除限制
- 新ICT,让城市更智慧 —— 华为智慧城市生态圈行动计划发布会即将于7月15日在苏州举办
- 5G Americas主席Chris Pearson:提出15个5G建议 积极推进测试工作
- 非常实用的15款开源PHP类库
- 【LeetCode】15. 3Sum
- 【蓝桥杯单片机组模块】15、PWM学习(总结版)
- 周期-14. 最大公约数与最小公倍数(15)
- Greenplum函数 - 身份证号15位转18位