原题链接:http://oj.leetcode.com/problems/3sum-closest/
这道题是Two
Sum的扩展,brute force时间复杂度为O(n^3), 对每三个数进行比较。这道题和Two
Sum有所不同,使用哈希表的解法并不是很方便,因为结果数组中元素可能重复,如果不排序对于重复的处理将会比较麻烦,因此这道题一般使用排序之后夹逼的方法,总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n),代码如下:
public ArrayList<ArrayList<Integer>> threeSum(int[] num)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(num==null || num.length<=2)
return res;
Arrays.sort(num);
for(int i=num.length-1;i>=2;i--)
{
if(i<num.length-1 && num[i]==num[i+1])
continue;
ArrayList<ArrayList<Integer>> curRes = twoSum(num,i-1,-num[i]);
for(int j=0;j<curRes.size();j++)
{
curRes.get(j).add(num[i]);
}
res.addAll(curRes);
}
return res;
}
private ArrayList<ArrayList<Integer>> twoSum(int[] num, int end,int target)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(num==null || num.length<=1)
return res;
int l = 0;
int r = end;
while(l<r)
{
if(num[l]+num[r]==target)
{
ArrayList<Integer> item = new ArrayList<Integer>();
item.add(num[l]);
item.add(num[r]);
res.add(item);
l++;
r--;
while(l<r&&num[l]==num[l-1])
l++;
while(l<r&&num[r]==num[r+1])
r--;
}
else if(num[l]+num[r]>target)
{
r--;
}
else
{
l++;
}
}
return res;
}
注意,在这里为了避免重复结果,对于已经判断过的数会skip掉,这也是排序带来的方便。 这道题考察的点其实和Two
Sum差不多,Two
Sum是3Sum的一个subroutine, 不过更加综合一些,实现上更加全面,需要注意细节,面试中比较常见的一道题。此题更加复杂的扩展是4Sum,请参见4Sum -- LeetCode.
分享到:
相关推荐
Leetcode-解决方案-CSharp ***此存储库将包含 C# 中许多 Leetcode 问题的解决方案 收集雨水 - Leetcode 42 (Hard) 文本对齐 - Leetcode 68(硬) 买卖股票的最佳时机 III - Leetcode 123 (Hard) 买卖股票的最佳时机 ...
3sum leetcode-curation-topical 精选 Leetcode 问题,按主题/概念分类。 我的策展标准是问题必须是有价值的,而不仅仅是为了难而难。 有价值的问题通常可以以不同的时间/空间效率(通过使用各种数据结构)以多种...
leetcode-js-tdd leetcode 勇士的简单样板 如何使用 克隆这个 repo 在你的 vscode 中安装 配置扩展以使用 repo 中的problems文件夹 使用1.two-sum.js案例导出解决方案 module . exports = { // ignore: true, fn : ...
3sum2.cpp - 3sum.cpp - BST_from_preorder_traversal.cpp - 2sum.cpp - remove_adjacent_duplicates.cpp - 子集.cpp - 子集_2.cpp - Remove_Nth_Node_From_End_of_List.cpp - invert_Binary_Tree.cpp - 对称树.cpp ...
leetcode-练习 算法实践 15. 3和 给定一个由 n 个整数组成的数组 nums,nums 中是否有元素 a、b、c 使得 a + b + c = 0? 在数组中找到所有唯一的三元组,其总和为零。 示例输入: [-1, 0, 1, 2, -1, -4] 示例输出:...
leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...
leetcode-问题-爬虫 目录由cd problems && npx leetcode-problems-crawler -r 1-10生成cd problems && npx leetcode-problems-crawler -r 1-10 用法 爬行问题1到5: $ npx leetcode-problem-crawler -r 1-5 爬行问题...
leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...
2Sum->3Sum(hash) 2Sum Less Than K->3Sum Closet->3Sum Smaller(两个指针接近) 找到重复的号码 两个指针: 链表循环 BF: DP: 数学: i^0=i;i^i=0 单号->单号2->单号3 n&n-1 例 12。 1 位数 13. 汉明距离 二...
leetcode-machine-swift :SOS_button: 请帮助在Sources/leetcode-machine-swift/leetcode.swift设置所有 leetcode 问题。 :SOS_button: 在 swift 编码时有 xcode 总是好的。 利用自动补全、类型检查...功能可以帮助...
leetcode-训练 算法训练。 java $: javac hello.java java $: java hello c $: gcc hello.c 如果没有错误会生成a.out 可执行文件 c $: ./a.out leetcode cli leetcode version leetcode help leetcode help user ...
leetcode 2 和 c 938.-BST-C-Leetcode 的范围总和 给定二叉搜索树的根节点和两个整数 low 和 high,返回值在包含范围 [low, high] 内的所有节点的值之和。 示例 1: 输入:root = [10,5,15,3,7,null,18],低 = 7,高...
leetcode编辑器leetcode-问题 自定义代码演示 leetcode 编辑器配置 代码文件名: $ ! velocityTool . camelCaseName(${question . titleSlug}) 代码模板: ${question . content} package ...Sum ...t
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
https://leetcode-cn.com/problems/two-sum/ 难度 : 简单 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。...
leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: ...3Sum - 效果不错,但仍需调整; O(n2) 复杂度; 花了~51ms 盛水最多的容器; O(n) 复杂度 难的: ?
SumZero ( int n ) { var arr = new int [ n ]; int j = 0 ; int x = 1 ; for ( int i = 0 ; i < n / 2 ; i ++ ) { arr [ j ++ ] = x ; arr [ j ++ ] = - 1 * x ; x ++ ; } if ( n % 2 == 1 ) arr [ j ] = 0 ; ...
3sum-0015 买卖股票的最佳时机-0121 最多水的容器-0011 contains-duplicate-0217 find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个...