题目:
Given an arraySofnintegers, find three integers inSsuch 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).
翻译:给定一个nums整型数组,和一个目标和target,找出数组中三个数的和最接近target,返回这个和即可
思路:和threeSum差不多,只不过不用标记这三个数的位置,只需返回三个数的和与target 相差的最小值。
求和的时候采用Twosum做法,此时target = target -num[i];然后返回2个数的和与新的target相差的最小值
注意: 表示相差最小值的时候 一定要用绝对值。即Math.abs()。
代码:
public static int threeSumClosest(int[] nums, int target) {
if(nums == null || nums.length < 3)
return Integer.MIN_VALUE;
Arrays.sort(nums);
int min = nums[0] + nums[1] + nums[2] - target;//最小间距
for(int i = 0 ; i < nums.length-2;i++)//保证nums.length-1 和nums.length-2
{
int close= twoSum(nums,i+1,target -nums[i]);//计算剩下2个数最接近值
if(Math.abs(min) > Math.abs(close))
min = close;
}
return target+min;
}
public static int twoSum(int []num,int start, int target)
{
int min = num[start] + num[start+1] -target;//找到最小间距
int l = start;
int r = num.length-1;
while(l < r)
{
if(num[l]+num[r]==target)//如果等于返回
return 0;
int close = num[l] + num[r] -target;
if(Math.abs(close) <Math.abs(min))
min = close;
if(num[l]+num[r] > target)
{
r--;
}
else l++;
}
return min;
}
最近复习网络安全,加上五一放假,刷题断了一些天,罪过罪过!
无奈过些日子还有UML考试。 一定要坚持!!!
分享到:
相关推荐
c# C#_Leetcode编程题解之第16题最接近的三数之和
python python_leetcode面试题解之第16题最接近的三数之和
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 ...
c语言 c语言_c语言编程基础之leetcode题解第16题最接近的三数之和
c++ c++_c++编程基础之leetcode题解第16题最接近的三数之和
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
python python_leetcode面试题解之三数之和_3sum
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).方法一 先排序,再利用双指针,类似于三数之和func threeSumClose
java java_leetcode面试题解双指针之第16题最接近的三数之和
Leetcode two sum java 解法
问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的答案(index1 和 index2)不是从零...
个数字的所有可能组合,并找出满足请求的组合。 这该怎么做? 我们将遍历数组中的每个元素,对于每个元素,我们将搜索其后面的所有数字:是否有 2 个数字之和等于该元素的相反数字? 如果有,请将这两个数字附加到...
16 | [3 Sum Closest](https://leetcode.com/problems/3sum-closest/) | [C++](./C++/3sum-closest.cpp) [Python](./Python/3sum-closest.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 18| [4 Sum]...
2sum leetcode 2SUM 使用以前的地图最快的 2Sum O(N) 使用 unordered_map 比 map 快 以前的地图 là gì ? 上一张地图 đơn giản là 地图 nhưng thay vì ta cần một vòng for để khởi tạo 地图 thì ta ...
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 ...
python python_leetcode面试题解之两数之和TwoSum
16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted ...
//给定一个整数数组和一个目标值,找出数组中和为目标值的两个数 //你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用 //示例: //给定 nums = [2, 7, 11, 15], target = 9 //因为 nums[0] + nums[1] = ...