原题链接:http://oj.leetcode.com/problems/3sum-closest/这道题跟3Sum很类似,区别就是要维护一个最小的diff,求出和目标最近的三个和。brute
force时间复杂度为O(n^3),优化的解法是使用排序之后夹逼的方法,总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n),代码如下:
public int threeSumClosest(int[] num, int target) {
if(num == null || num.length<=2)
return Integer.MIN_VALUE;
Arrays.sort(num);
int closest = num[0]+num[1]+num[2]-target;
for(int i=0;i<num.length-2;i++)
{
int cur = twoSum(num,target-num[i],i+1);
if(Math.abs(cur)<Math.abs(closest))
closest = cur;
}
return target+closest;
}
private int twoSum(int[] num, int target, int start)
{
int closest = 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 diff = num[l]+num[r]-target;
if(Math.abs(diff)<Math.abs(closest))
closest = diff;
if(num[l]+num[r]>target)
{
r--;
}
else
{
l++;
}
}
return closest;
}
这道题具体的考察点可以参见3Sum,稍微变体一下,其实区别不大。此题更加复杂的扩展是4Sum,请参见4Sum
-- LeetCode.
分享到:
相关推荐
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
3sum-closest 49组字谜 更新 2020-1-16 123 已完成问题447 个回旋镖 更新 2020-1-17 124 已完成问题149 最大单线点数 更新 2020-1-18 126题已完成 56 个合并间隔 86 分区列表 98 验证二进制搜索树 9 审查问题 第105...
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-...
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
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题库 LeetCode 题解合集 本仓库展示了LeetCode题库中部分题目的解法(持续更新),所有代码均采用C++编写...3Sum.cpp 最接近的三数之和 3Sum Closest .cpp 20 有效的括号 Valid Parentheses.cpp 22 括号生成 G
leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。 编号 中文题目 ...3Sum 中等 16 3Sum Closest 中等 17 Letter Combinations of a Phone Number DFS 中等 18 4Sum 中等 19 Remo
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_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中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash ...3 ...3Sum Closest 最接近的三数之和 two pointers,array 21 Merge Two Sorted Lists 合并两个有序链表 lin
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 ...
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 和 c LeetCode_record(C++) Leetcode 问题 我已经完成了解决方案和简要说明。 目前,我正在做热门面试问题。 完毕 ...15-3总和 16-3Sum Closest(无解,类似3Sum) 454-4和II 正在做 18-4和
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...
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
gas station ...p0016_3sum_closest; // pub mod p0018_4sum; pub mod p0003_longest_substring_without_repeating_characters; pub mod p0005_longest_palindromic_substring; pub mod p0007_reverse_int
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
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
[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....
java lru leetcode Java算法问题 托管来自 LintCode、LeetCode 等算法问题的 Java 解决方案。 一旦出现新问题或新测试用例,我将尝试...[3Sum Smaller.java]( Smaller.java) Java 6 [4 Sum.java]( Sum.java) 中等的 J