【题目】
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).
【题意】
给定n个整数的数组S,寻找S中三个整数,使得总和最接近给定的目标。
返回三个整数的总和。
你可以假设每个输入将有一个确切的解决方案。
【分析】
题目思路和上题差不多。
先排序,二分查找来左右逼近。
对于a + b + c ,对a规定一个数值时,采用二分查找b,c使Sum= a + b + c 最接近target。
a可以取数组S中任何一个数值,使得有多个Sum,CurClosest =abs(target - Sum)求Min(CurClosest),即最接近的那个。
【代码】
/*********************************
* 日期:2014-01-18
* 作者:SJF0115
* 题号: 3Sum Closest
* 来源:http://oj.leetcode.com/problems/3sum-closest/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <LIMITS.H>
using namespace std;
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
int i,j,result,start,end,Sum,CurClosest,MinClosest = INT_MAX;
int Len = num.size();
//排序
sort(num.begin(),num.end());
for(i = 0;i < Len-2;i++){
start = i + 1;
end = Len - 1;
//二分查找
while(start < end){
//a + b + c
Sum = num[i] + num[start] + num[end];
//接近度
CurClosest = abs(target - Sum);
//更新最接近的Target
if(CurClosest < MinClosest){
MinClosest = CurClosest;
result = Sum;
}
//相等 -> 目标(唯一一个解)
if(target == Sum){
return Sum;
}
//大于 -> 当前值小需要增大
else if(target > Sum){
start ++;
}
//小于 -> 当前值大需要减小
else{
end --;
}
}//while
}//for
return result;
}
};
int main() {
int result;
Solution solution;
vector<int> vec;
vec.push_back(-1);
vec.push_back(2);
vec.push_back(1);
vec.push_back(-4);
result = solution.threeSumClosest(vec,-4);
printf("Target:%d\n",result);
return 0;
}
分享到:
相关推荐
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
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 ...
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]...
leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。 编号 中文题目 ...3Sum 中等 16 3Sum Closest 中等 17 Letter Combinations of a Phone Number DFS 中等 18 4Sum 中等 19 Remo
java lru leetcode :ice_cream: ...Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
leetcode题库 LeetCode 题解合集 本仓库展示了LeetCode题库中部分题目的解法(持续更新),所有代码均采用C++编写...3Sum.cpp 最接近的三数之和 3Sum Closest .cpp 20 有效的括号 Valid Parentheses.cpp 22 括号生成 G
leetcode中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash ...3 ...3Sum Closest 最接近的三数之和 two pointers,array 21 Merge Two Sorted Lists 合并两个有序链表 lin
3sum_closest 4sum 添加二进制 添加数字 添加字符串 add_two_numbers balance_binary_tree best_time_to_buy_and_sell_stock best_time_to_buy_and_sell_stock_II binary_tree_inorder_traversal binary_tree_level_...
leetcode_0016_three_sum_closest.c leetcode_0018_four_sum.c : not ready leetcode_0026_remove_duplicates.c 27, 80, 283 leetcode_0031_next_permutation.c leetcode_0033_search_rotate.c : binary ...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
3Sum.js 16 3Sum Closest.js 电话号码的 17 个字母组合.js 19 从 List.js 的末尾删除第 N 个节点 20 个有效括号.js 21 合并两个有序Lists.js 22 生成括号.js 23 合并 k 排序 Lists.js Pairs.js 中的 24 个交换节点 k...
18 3Sum Closest 57 19 String to Integer (atoi) 59 20 Merge Sorted Array 61 ... ... 231 Counting Bits 561 232 Maximum Product of Word Lengths 563 233 Gray Code 565 234 Permutations 567 235 Permutations...
leetcode 530 ** LeetCode ...3Sum 016 3Sum Closest 017 Letter Combinations of a Phone Number 018 4Sum 020 Valid Parentheses 022 Generate Parentheses 028 Implement strStr() 031 Next Permutat
leetcode 和 oj #问题列表(按标题升序) 标题|添加日期|AC 利率 ---|---|---|--- 3Sum |2012-01-17|16.4% 3Sum Closest|2012-01-18|26.8% 4Sum|2012-01-26 |21.3% 二进制加法|2012-04-02|25.6% 两个数相加|2011-11-...
lru cache ...3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next Permutation 公式 13 Permutation Sequence 公式 14 Valid Sudoku 15 Trapping Rain W
[3Sum Smaller.java]( Smaller.java) Java 6 [4 Sum.java]( Sum.java) Java 7 Java 8 [添加和搜索 Word.java](和搜索 Word.java) Java 9 [添加Binary.java](Binary.java) Java 10 [加两个数II.java]( 两个数II....
leetcode卡 LeetCodeMing 记录自己日常刷题LeetCode的点滴,技术改变世界,FOR PEACE 同时也是在参与ARTS打卡计划,记录自己的日常 LeetCodeMing ...Closest 18.4Sum Other 306.Additive Number [官网链接] ()
java lru leetcode Leetcode 问题的解决方案 问题 解决方案 0001_Two_Sum 0002_Add_Two_Numbers 0003_Longest_Substring_Without_Repeating_Characters ...0016_3Sum_Closest 0017_Letter_Combinations_of_a_Phone_N
java lru leetcode Java算法问题 托管来自 LintCode、LeetCode 等算法问题的 Java 解决方案。 一旦出现新问题或新测试用例,我将尝试...[3Sum Smaller.java]( Smaller.java) Java 6 [4 Sum.java]( Sum.java) 中等的 J
leetcode 2 和 c LeetCode_record(C++) Leetcode 问题 我已经完成了解决方案和简要说明。 目前,我正在做热门面试问题。 完毕 ...15-3总和 16-3Sum Closest(无解,类似3Sum) 454-4和II 正在做 18-4和