【题目】
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
* 题号: 16.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;
}
分享到:
相关推荐
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
Leetcode two sum java 解法
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: 2sum - 带有未排序的数组; O(n) 复杂度; 花了~3ms 2sum - 使用排序数组; O(n) 复杂度 罗马转整数; O(n) 复杂度 合并...
leetcode 2sum # Programming-Problems This will have many problems from all over the web, As of writing this readme there is Haskell 99: 28 finished + Huffman Coding LeetCode: LC1: 2Sum [Easy] LC2: Add...
leetcode 2sum 2总和 力码研究1
第 338 章力码 LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without ...15.3Sum 16.3Sum Closest 17.Letter Combinations of a Phone Number 18.4Sum 19.Remove Nth Node From End
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...
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
3sum leetcode-curation-topical 精选 Leetcode 问题,按主题/概念分类。 我的策展标准是问题必须是有价值的,而不仅仅是为了难而难。 有价值的问题通常可以以不同的时间/空间效率(通过使用各种数据结构)以多种...
lru cache leetcode #算法解题报告 主要记录我每天做的题目,包括leetcode, 剑指offer等在线编程平台,以前做过...16.3Sum Closest 19.Remove Nth Node From End of List 20.Valid Parentheses 21.Merge Two Sorted L
答案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 ...
leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。 编号 中文题目 英文题目 ...Sum ...3Sum ...Closest 中等 17 Letter Combinations of a Phone Number DFS 中等 18 4Sum 中等 19 Remo
leetcode卡 LeetCodeMing 记录自己日常刷题LeetCode的点滴,技术改变世界,FOR PEACE 同时也是在参与ARTS打卡计划,记录自己的日常 ...16.3Sum Closest 18.4Sum Other 306.Additive Number [官网链接] ()
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
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 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...