15. 3Sum、16. 3Sum Closest和18. 4Sum
15 3sum
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]
]
思考:1、想了很久,不知道怎么做。只能想到时间复杂度比较高的做法。在网上查到,这个3sum问题是比较经典的,其解法基于2sum。2sum问题是给定一个排好序的数组,问有哪些两个元素相加为
0。解法是一个下标指向第一个,另一个下标指向最后一个。
有如下结论及其规则:
一、如果num[1]+num[n]>0,那么2和n的和大于0,3和n的和也会大于0。等等。所以就没必要再去计算以最后一个为右边界的组合。考虑1,..,n-1这个范围内的组合,即移动后一个。
二、如果num[1]+num[n]<0,那么1和n-1的和,1和n-2的和也会小于0。等等。所以就没必要去计算以1为左边界的组合。考虑2,...,n这个范围内的组合,即移动前一个下标。
不断进行这个操作,最终遍历所有可能的组合,而不是每个组合。 3sum问题可以分解成2sum。取出数组第一个元素X,在剩下的数组里找到两数之和为-X,这就是2sum问题。 由于c语言不支持动态添加元素,所以用c++可能更方便一些,故实现如下。ps:用c语言做了一下,一直free内存那里出问题。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int> > ans;
int index1,index2;
if(nums.size()<) return ans; sort(nums.begin(), nums.end()); for (int i = ; i <= nums.size()-; i++) {
if(i!= && nums[i-]==nums[i]) continue; index1 = i+;
index2 = nums.size()-;
/*if(i==0) {
index1 = 1;
index2 = nums.size()-1;
}
else if (i== nums.size()-1) {
index1 = 0;
index2 = nums.size()-2;
}else {
index1 = 0;
index2 = nums.size()-1;
}*/ while(index1<index2) {
if(nums[i]+nums[index1]+nums[index2]==) {
int sol[] = { nums[i], nums[index1], nums[index2] };
ans.push_back(vector<int> (sol, sol + ));
//printf("i is %d.index1 is %d.index2 is %d.\n", i,index1,index2);
index1++;while(nums[index1]==nums[index1-]) index1++;
index2--;while(nums[index2]==nums[index2+]) index2--;
}else if (nums[i]+nums[index1]+nums[index2]>) {
index2--;
}else {
index1++;
}
}
}
return ans;
}
};
16 3sum closet
Given an array nums
of n integers and an integer target
, find three integers in nums
such that the sum is closest to target
. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
和上面是简单变形关系,所用的原理一样。因为此次并不需要返回数组的数组,所以又用c语言来表示我的行为。
void my_qsort(int *nums, int index1, int index2) {
if(index1==index2) return; int pre,last;
int tmp; pre = index1;
for(last=index1+; last<=index2; last++) {
if(nums[last]<nums[index1]) {
pre++;
tmp = nums[pre];
nums[pre] = nums[last];
nums[last] = tmp;
}
}
tmp = nums[index1];
nums[index1] = nums[pre];
nums[pre] = tmp; if(pre==index1) {
my_qsort(nums, index1+, index2);
}else if(pre==index2) {
my_qsort(nums, index1, index2-);
}else {
my_qsort(nums, index1, pre-);
my_qsort(nums, pre+, index2);
} } int threeSumClosest(int* nums, int numsSize, int target) {
int ret,index1,index2,tmp;
my_qsort(nums, , numsSize-);
for(int i = ; i<numsSize; i++)
printf("%d ", nums[i]);
printf("\n");
ret = nums[] + nums[] + nums[];
for(int i=; i<=numsSize-;i++) {
index1 = i+;
index2 = numsSize-;
while(index1<index2) {
tmp = nums[i] + nums[index1] + nums[index2];
if(tmp == target) return tmp;
if(abs(tmp-target)<abs(ret-target)) ret = tmp;
if(tmp>target) {
index2--;
}else if(tmp < target) {
index1++;
}
}
} return ret;
}
18. 4Sum
Given an array nums
of n integers and an integer target
, are there elements a, b, c, and d in nums
such that a + b + c + d = target
? Find all unique quadruplets in the array which gives the sum of target
.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [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]
]
思考:首先按一定顺序取前两个数,共有(n-3)*(n-2)个组合,对于剩下的两个数就用首尾指针进行移动检查。
这里我有一个小小的优化。看下line 12行的代码,如果nums[i]大于0,nums[i]>terget,那么后面的三个数一定大于0。既然后面的三个数都大于0,nums[i]加上大于的0
一定大于target。所以就没有必要再继续检查。第15行代码同理。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans; sort(nums.begin(), nums.end()); int len = nums.size();
int i,j,k,l; for(i=; i<=len-; i++) {
if(nums[i]>target && nums[i]>=) continue;
if(i>= && nums[i]==nums[i-]) continue;
for(j=i+; j<=len-; j++) {
if(nums[i]+nums[j]>target && nums[j]>=) continue;
if(j>=i+ && nums[j]==nums[j-]) continue;
k = j + ;
l = len - ;
while(k<l) {
if(nums[i]+nums[j]+nums[k]+nums[l]>target) {
l--;
}else if(nums[i]+nums[j]+nums[k]+nums[l]<target){
k++;
}else {
int sol[] = { nums[i], nums[j], nums[k],nums[l] };
ans.push_back(vector<int> (sol, sol + ));
k++;
while(nums[k]==nums[k-]) k++;
l--;
while(nums[l]==nums[l+]) l--;
} } }
}
return ans;
}
};
最新文章
- 既不删除, 也不生成DS_store
- 【2016-07-11】Qt远程部署失败,提示";没有那个文件或目录";的解决方法
- DB2 Unload 的时候遇到B37-04
- Windows server2003 + sql server2005 集群配置安装
- SCVMM之Windows Server2012 R2新功能
- ffmpeg关于aac解码
- Python读取PDF内容
- 机器学习学习-Types of learning
- 【教程】发布NAServer到ArcGIS Server 10.4上[超详细]
- Linux下使用gcc编程初体验
- CentOS 6.5 网络服务器功能的实现②:运用光盘(镜像)制作一个本地yum源
- 安装 kubernetes v1.11.1
- Android学习之Button按钮在程序运行时全部变大写的处理
- BZOJ1178 [Apio2009]CONVENTION会议中心 贪心 set
- ace富文本编辑器
- Node操作MongoDB并与express结合实现图书管理系统
- 【转】【Mac】invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at: /Library
- Ubuntu14.04(server amd 64)编译安装 ceres-solver
- DevExpress v18.1新版亮点——ASP.NET篇(二)
- awk 截取某段时间的日志
热门文章
- nginx启动报错nginx: [error] open() ";/usr/local/etc/nginx/logs/nginx.pid"; failed
- NCE L3
- linux传输文件-sftp
- Python爬虫beautifulsoup4常用的解析方法总结(新手必看)
- Centos7 使用Docker 部署mssql 2017
- java 入门如何设计类
- PHP0023:PHP 相册管理案例
- Django 表关系的创建
- 避免js重复加载的问题
- win10自带邮箱如何使用?win10自带邮箱如何同步qq邮箱邮件?