LeetCode OJ:Three Sum(三数之和)
2024-09-28 04:53:24
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:
(-1, 0, 1)
(-1, -1, 2) 大体的思想先将数组排序,从小到大取vector中的数first,再从剩下的数中取和等于 0 - first 的数即可。下面是代码(一开始没想出来,然后参考了别人的解法在写出来,一般的三层循环谁都能想到,但是时间复杂度太高,这里的这个时间复杂度应该是O(N^2),还是可以接受的)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> result;
int sz = nums.size();
sort(nums.begin(), nums.end());
for (int i = ; i < sz - ; ++i){
twoSum(nums, i + , - nums[i], result);
while(nums[i] == nums[i + ]) ++i;//这一步要注意,防止得出重复的vector
}
return result;
} void twoSum(vector<int> & nums, int start, int value, vector<vector<int>> & ret)
{
int beg = start;
int end = nums.size()-;
while (beg < end){
int sum = nums[beg] + nums[end];
if (sum < value)
beg++;
else if (sum > value)
end--;
else{
ret.push_back(vector<int>{nums[start - ], nums[beg], nums[end]});
while (nums[beg + ] == nums[beg]) beg++;//这一步的处理应该注意,防止出现相同的vector
while (nums[end - ] == nums[end]) end--;
beg++, end--;
}
}
}
};
java版的代码如下所示:
(由于不太熟悉ArrayList和List之间的关系,写起来感觉各种坑爹啊,注意下List和ArrayList之间的各种转换就可以了,代码如下):
public class Solution {
List<List<Integer>> ret = new ArrayList<List<Integer>>(); public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
for(int i = 0; i < nums.length - 2; ++i){
twoSum(nums, i+1, 0 - nums[i]);
while(i < nums.length - 2 && nums[i] == nums[i+1])
++i;
}
return ret;
} public void twoSum(int[] nums, int start, int value)
{
int beg = start;
int end = nums.length - 1;
while(beg < end){
if(nums[beg] + nums[end] == value){
List<Integer> list = new ArrayList<Integer>();
list.add(nums[start - 1]);
list.add(nums[beg]);
list.add(nums[end]);
ret.add(list);
while(beg < end && nums[beg+1] == nums[beg])
beg++;
while(beg < end && nums[end-1] == nums[end])
end--;
beg++;
end--; }else if(nums[beg] + nums[end] > value){
end--;
}else{
beg++;
}
}
}
}
PS:同样的4Sum问题也可以转换成上面的3Sum问题,从而递归的求解,KSum问题也是一样
最新文章
- 【jq】c#零基础学习之路(1)Hello World!
- nginx相关
- Codeforces 697A - Pineapple Incident
- mongodb备忘
- logo上线
- SMTP sendMail 失败解决办法
- 290.	Word Pattern
- JavaScript学习笔记(13)——BOM
- xml技术DTD约束定义
- iOS应用性能调优的25个建议和技巧【转】
- js 按元素向数组中最佳删除元素
- Spring-----3、Spring的核心机制(依赖注入)
- Weblogic+apache多虚拟主机
- ISP PIPLINE (十四) AE(自动曝光)
- Vue.js的简介
- map,set和weakmap,weakset
- [转]php模拟post提交请求,调用接口
- DOM的基本操作
- hiho一下 第144周
- NodeJs使用async让代码按顺序串行执行
热门文章
- Oracle 11g数据库详解(3)
- HTML5 canvas绘图基本使用方法
- corethink功能模块探索开发(十七)opencmf.php 配置文件
- table实现 js数据访问 传递json数据用render_to_response
- eclipse 安装 spring boot suite 插件遇到的问题
- HDU - 6395 Sequence (分块+快速矩阵幂)
- 牛客网暑期ACM多校训练营(第一场)- J Different Integers (莫队)
- ubuntu中Eclipse-cpp编译MySQL源码
- Apache 工作模式配置优化
- CSS3 Loading进度条加载动画特效