Leetcode 4Sum
2024-10-10 10:58:28
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
与3sum一样
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > res;
int n = num.size();
if( n < ) return res;
sort(num.begin(),num.end());
for(int i = ; i < n-; ++ i){
if(i != && num[i]== num[i-]) continue;
for(int j = i+; j < n-; ++ j){
if(j!=i+ && num[j] == num[j-] ) continue;
int start = j+, end = n-;
while(start < end){
int sum = num[i]+num[j]+num[start]+num[end];
if(sum > target) end--;
else if(sum < target) start++;
else{
vector<int> a;
a.push_back(num[i]);a.push_back(num[j]);
a.push_back(num[start]);a.push_back(num[end]);
res.push_back(a);
do{start++;}while(start < end && num[start] == num[start-]);
do{end--;}while(start < end && num[end] == num[end+]);
}
}
}
}
return res;
}
};
最新文章
- Does the OpenSceneGraph have a native file format?
- BZOJ 1179 Atm 题解
- 提高Java代码质量:使用枚举定义常量(转)
- Spring MVC 环境搭建(二)
- HDU 5583 Kingdom of Black and White 水题
- composer安装yii2或者laravel报错
- configure文件中判断某函数或库是否存在的一个方法
- 理解screenX clientX pageX概念
- hibernate多对一的操作解析
- oracle表空间创建及管理
- 探索Oracle之数据库升级七 11gR2 to 12c 升级完毕后插入PDB
- jquery 如何动态添加、删除class样式方法介绍_jquery_脚本之家
- java面试题(一)
- 异步请求之ajax
- python待学习内容
- 在anguler项目中引用fullCalendar
- 动手动脑(lesson 8)
- jira7.3.6添加导出excel的按钮
- sgu
- JBoss 系列四十九:JBoss 7/WildFly 中端口使用列表