`
betakoli
  • 浏览: 168444 次
社区版块
存档分类
最新评论

LeetCode 3Sum Closest

 
阅读更多

Given an array S of n integers, find three integers in S such 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).

 

题意:从数组中找出3个值,使得其相加结果最近似于target值。

地址:https://oj.leetcode.com/problems/3sum-closest/

 

思路:和3sum类似,只不过是求相似值。

 

public int threeSumClosest(int[] num, int target) {
		rank(num);
//value是与target值差值的绝对值,在后面会用到
		int value=Integer.MAX_VALUE;
		for(int i=0;i<num.length-2;i++)
		{
			if(i>0&&num[i]==num[i-1])
				continue;
			int j=i+1;
			int k = num.length-1;
			
			while(j<k)
			{
				int sum = num[i]+num[j]+num[k];
				value = Math.abs(sum-target)<Math.abs(value)?sum-target:value;
				if(sum-target==0)
				{
					return target;
				}else if(sum-target>0)
				{
					k--;
					if(num[k]==num[k+1])
						k--;
					continue;
				}else
				{
					j++;
					if(num[j]==num[j-1])
						j++;
					continue;
				}
			}
		}
		return value+target;
    }
	
	
	public void rank(int[] sum)
	{
		for(int i=0;i<sum.length-1;i++)
		{
			for(int j=i+1;j<sum.length;j++)
			{
				if(sum[i]>sum[j])
				{
					int temp = sum[i];
					sum[i]=sum[j];
					sum[j]=temp;
				}
			}
		}
	}

 

分享到:
评论

相关推荐

    js-leetcode题解之16-3sum-closest.js

    js js_leetcode题解之16-3sum-closest.js

    c语言-leetcode 0016-three-sum-closest.zip

    c c语言_leetcode 0016_three_sum_closest.zip

    leetcode答案-LeetCode_1_TwoSum:LeetCode_1_TwoSum

    答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...

    程序员面试宝典LeetCode刷题手册

    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 刷题汇总1

    * 3Sum最近(3Sum Closest):找到数组中三个元素的和最近目标值的元素。 * 4Sum(4Sum):找到数组中四个元素的和等于目标值的元素。 这些知识点涵盖了算法设计、数据结构、数学运算、字符串操作、链表操作、栈...

    js代码-16. 3Sum Closest

    描述中的 "3Sum Closest" 是指三数之和最接近某个特定值的问题,通常在LeetCode等在线编程平台上被讨论。 这个问题的基本设定是:给定一个整数数组 `nums` 和一个目标整数 `target`,你需要找出数组中三个整数,...

    leetcode2sumc-leetcode:JavaScript版本leetcode中文版代码

    leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。 编号 中文题目 ...3Sum 中等 16 3Sum Closest 中等 17 Letter Combinations of a Phone Number DFS 中等 18 4Sum 中等 19 Remo

    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中文版

    5. **2.1.9 3Sum Closest**:给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。 6. **2.1.10 4Sum**:给定一个包含 n 个整数的...

    LeetCode前400题Java精美版

    16. **3Sum Closest** (Medium): 找出数组中三个数的和最接近目标值的组合。在3Sum的基础上,需要调整指针移动策略以寻找最接近的和。 这些题目覆盖了数据结构、算法、字符串处理、数学逻辑等多个方面,对于提升...

    LeetCode答案大全

    16. 3Sum Closest:与3Sum类似,但需要找到和为目标值最近的三个数的组合。 17. Letter Combinations of a Phone Number:电话号码的字母组合。这是回溯算法的一个典型应用。 18. 4Sum:找到所有和为特定值的不...

    javalruleetcode-LeetCode::lollipop:个人LeetCode习题解答仓库-多语言

    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

    java-leetcode面试题解双指针之第16题最接近的三数之和.zip

    其中,第16题“最接近的三数之和”(3Sum Closest)是一道常见的双指针问题,常出现在面试中以考察应聘者对算法的理解和应用能力。这个题目的目标是找到数组中三个数的和,使得它们的和最接近给定的目标值。 解题的...

    算法刷题笔记leetcode/lintcode

    - 3 Sum Closest(三数之和最接近) - Remove Duplicates from Sorted Array(删除有序数组中的重复项) - Remove Duplicates from Sorted Array II(删除排序数组中的重复项II) - Merge Sorted Array(合并两...

    Python_leetcode.zip

    "closest-binary-search-tree-value-ii.py"是一个涉及二叉搜索树遍历的问题。在二叉搜索树中寻找最近的两个节点,要求改变路径中的一个节点。Python的递归和树遍历策略在这里得到应用,展示了Python在数据结构操作上...

    leetcode刷题列表

    例如,树的层级遍历(Levelorder Traversal)、判断树的对称性(Symmetric Tree)、找到二叉搜索树中距离某个值最近的节点(Closest Binary Search Tree Value)等。这些题目通常要求编写者熟悉树的结构和遍历方法,...

    _leetcode-python.pdf

    - 3Sum / 3Sum Closest / 4Sum: 这些题目都涉及到在数组中寻找具有特定和的数字组合,这通常需要用到双指针技术。 - Remove Nth Node From End of List: 给定一个链表,删除链表中的第n个节点。 - Valid Parentheses...

    leetcode中文版-LeetCode:LeetcodeC++/Java

    leetcode中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash ...3 ...3Sum Closest 最接近的三数之和 two pointers,array 21 Merge Two Sorted Lists 合并两个有序链表 lin

Global site tag (gtag.js) - Google Analytics