3Sum Closest
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).
这道题和3Sum差不多,不过也有不一样的,主要是:
1 这里不用判断处理重复问题
2 要比较其中的三个数的和与目标数的差的大小。
class Solution {
public:
int threeSumClosest(vector<int> &num, int target)
{
switch (num.size())
{
case 0:
return 0;
case 1:
return num[0];
case 2:
return num[0] + num[1];
default:
break;
}
sort(num.begin(), num.end());
int closet = 0;
int sum = 0;
int i = 0, j = 0, k = num.size()-1;
int diff = INT_MAX;
for (i = 0; i < k-1; i++)
{
for (j = i+1; j < k;)
{
sum = num[i] + num[j] + num[k];
if (sum == target)
{
return sum;
}
if (abs(sum-target) < diff)
{
closet = sum;
diff = abs(sum - target);
}
if (sum < target)
{
j++;
}
else
{
k--;
}
}
}
return closet;
}
};
//2014-1-25 update8.24
class Solution125 {
public:
int threeSumClosest(vector<int> &num, int target)
{
int closest = INT_MAX;
int res = 0;
sort(num.begin(), num.end());
for (int i = 0; i < num.size(); i++)
{
for (int j = i+1, k = num.size()-1; j < k; )
{
int sum = num[i]+num[j]+num[k];
if (sum == target) return sum;
int t = abs(sum-target);
if (t<closest)
{
res = sum;
closest = t;
}
if (sum < target) j++;
else if (sum > target) k--;
}
while (i < num.size() && num[i] == num[i+1]) i++;
}
return res;
}
};
分享到:
相关推荐
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
Leetcode two sum java 解法
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).方法一 先排序,再利用双指针,类似于三数之和func threeSumClose
文章目录最接近的三数之和题目解题思路代码实现实现结果题外话 最接近的三数之和 题目来源:...与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). 解题思路 数组排序 + 双指针; 对数组进行排序,初
python python_leetcode面试题解之三数之和_3sum
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
c语言 c语言_c语言编程基础之leetcode题解第16题最接近的三数之和
c++ c++_c++编程基础之leetcode题解第16题最接近的三数之和
问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的答案(index1 和 index2)不是从零...
c# C#_Leetcode编程题解之第16题最接近的三数之和
python python_leetcode面试题解之第16题最接近的三数之和
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]...
python python_leetcode面试题解之两数之和TwoSum
java java_leetcode面试题解双指针之第16题最接近的三数之和
leetcode两数之和代码 题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个...
//给定一个整数数组和一个目标值,找出数组中和为目标值的两个数 //你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用 //示例: //给定 nums = [2, 7, 11, 15], target = 9 //因为 nums[0] + nums[1] = ...
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
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 khởi...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode