Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
题意就是给定一个数组,一个target,在数组中寻找一个三元组之和最接近target的值,这个题是之前3Sum的变形,不同的是这个题没有重复元素,而且设定解唯一。
我的思路是:跟之前的3sum一样,保留左右各一个pointer,遍历的时候,有left和right两个游标,left就从i+1开始,right就从数组最右length-1开始,如果i、left、right三个元素加起来等target,那么就可以加入结果的List中了,如果sum-target>0,那么说明sum比较大,right应该向左移动,反之left向右移动。
Talk is cheap>>
public int threeSumClosest(int[] num, int target) {
if (num == null || num.length < 3) {
return 0;
}
int min = Integer.MAX_VALUE;
int res=0;
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int left = i + 1;
int right = num.length - 1;
while (left < right) {
int sum = num[i] + num[left] + num[right];
// System.out.printf(i+" "+sum);
if (sum == target) {
return target;
}
if (min>=abs(sum-target)){
min = abs(sum-target);
res=sum;
}
if (sum-target>0){
right--;
}else {
left++;
}
}
}
return res;
}
public int abs(int a){
return Math.abs(a);
}
3Sum Closest——LeetCode的更多相关文章
-
3Sum Closest - LeetCode
目录 题目链接 注意点 解法 小结 题目链接 3Sum Closest - LeetCode 注意点 和3Sum那道题的target是0,这道题是题目给定的 要先计算误差再移动指针 解法 解法一:做法 ...
-
3Sum Closest leetcode java
题目: Given an array S of n integers, find three integers in S such that the sum is closest to a given ...
-
[LeetCode][Python]16: 3Sum Closest
# -*- coding: utf8 -*-'''__author__ = 'dabay.wang@gmail.com' 16: 3Sum Closesthttps://oj.leetcode.com ...
-
LeetCode之“散列表”:Two Sum &;&; 3Sum &;&; 3Sum Closest &;&; 4Sum
1. Two Sum 题目链接 题目要求: Given an array of integers, find two numbers such that they add up to a specif ...
-
LeetCode 16. 3Sum Closest(最接近的三数之和)
LeetCode 16. 3Sum Closest(最接近的三数之和)
-
LeetCode解题报告—— Container With Most Water &; 3Sum Closest &; Letter Combinations of a Phone Number
1. Container With Most Water Given n non-negative integers a1, a2, ..., an, where each represents a ...
-
LeetCode:3Sum, 3Sum Closest, 4Sum
3Sum Closest Given an array S of n integers, find three integers in S such that the sum is closest t ...
-
【leetcode】3Sum Closest
3Sum Closest Given an array S of n integers, find three integers in S such that the sum is closest t ...
-
LeetCode 15. 3Sum 16. 3Sum Closest 18. 4Sum
n数求和,固定n-2个数,最后两个数在连续区间内一左一右根据当前求和与目标值比较移动,如果sum<target,移动较小数,否则,移动较大数 重复数处理: 使i为左至右第一个不重复数:while ...
随机推荐
-
log4net写入mysql完整例子
1,创建表log CREATE TABLE `log` ( `id` int(11) NOT NULL AUTO_INCREMENT , `log_datetime` timestamp NO ...
-
rsync+sersync实现文件实时同步
前言: 一.为什么要用Rsync+sersync架构? 1.sersync是基于Inotify开发的,类似于Inotify-tools的工具 2.sersync可以记录下被监听目录中发生变化的(包括增 ...
-
【Android】如何使用安卓的logcat『整理』
logcat是Android中一个命令行工具,可以用于得到程序的log信息.开发调试和测试定位bug都挺有用哒 有两种方式可以达到查看log的目的. 一 Eclipse集成DDMS插件 1 安装ecl ...
-
python global 全局变量
http://blog.csdn.net/mldxs/article/details/8559973 __author__ = 'dell' def func(): global x print 'x ...
-
jQuery特效手风琴特效 手写手风琴网页特效
今天写一个简单的手风琴效果,不用插件,利用强大的jQuery,写一个手风琴效果. 页面预览,请点击这里预览: 手风琴预览 案例分析: html结构 就是一个大盒子里面放着5个li,每个li的小小是2 ...
-
C++该函数隐藏
只有基类成员函数的定义已声明virtualkeyword,当在派生类中的时间,以支付功能实现,virtualkeyword可以从时间被添加以增加.它不影响多状态. easy混淆视听,掩盖: ,规则例如 ...
-
ios学习之常见问题记录
使用Core Data的好处和缺点? 首先这是apple官方极力推荐的,使用它而不是SQLite.好处有大概这么几点:1.减少你model层的代码量,减少50%-70%.无需测试和优化.2.提供了内存 ...
-
java链接mysql添加中文和模糊查询
如下内容为转载 http://sunshinechen2008.blog.163.com/blog/static/107585374201162442643967/ mysql如果不对乱码处理 ...
-
docker整理
Docker的简单介绍 docker是什么 Docker 最初是 dotCloud 公司创始人 Solomon Hykes 在法国期间发起的一个公司内部项目,于 2013 年 3 月以 Apache ...
-
SpringMVC Controller 返回值几种类型
SpringMVC Controller 返回值几种类型 2016年06月21日 19:31:14 为who而生 阅读数:4189 标签: Controller 返回值类型spring mvc 更多 ...