[LeetCode][Java] 3Sum Closest「建议收藏」

[LeetCode][Java] 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).


题意:

给定一个包括n个整数的数组S,在数组中找出三个整数。使得这三个整数的和与目标值最为接近。

返回这三个整数的和。你能够假定对于每一个整数。都有确定的一个解。

    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).


算法分析:


  參考博客:http://www.zhuangjingyang.com/leetcode-3sum/

    和3Sum异曲同工。 只是这里我们要推断的条件不在是三个数字和为0而是和为一个更加接近target的数字。

    我们依旧採用3Sum的算法,若有三个数字x1 + x2 + x3 = result 我们所求的便是让result最接近target。

    因此对于num,首先排序。然后遍历每一个数字其下标大于自身的两个数字。然后设置两个全局变量 一个 minVal 用于记录其与target的距离,当距离减小时便更新result的新值。


AC代码:

<span style="font-size:12px;">public class Solution 
{
	private  int minVal = Integer.MAX_VALUE;
	private  int result = 0;
    public  int threeSumClosest(int[] num, int target) 
    {
    	Arrays.sort(num);
    	//if number is less than 3 or num is null it's can't be calc
    	if(num.length <3 ||  num ==null)
    		return target;
    	for(int i=0;i<num.length;i++)
    	{
    		if(i>0 && num[i] == num[i-1])
    			continue;
    		find(i,num,num[i],target);
    	}
    	return result;
    }
    public  void find(int index,int[] num,int target,int res)
    {
    	int l = index+1; //low is equal to index+1 just because we just search element that is bigger than itself
    	int r = num.length - 1;
    	while(l<r)
    	{
    		if( Math.abs(num[l] + num[r] + target - res) <= minVal)
    		{
    			minVal = Math.abs(num[l] + num[r] + target - res);//it's more closer
    			result = num[l] + num[r] + target;
    		}
    		if(num[l] + num[r] + target >res)
    			r--;
    		else
    			l++;
    	}
    }
}</span>



版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116237.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • R语言做小提琴图_小提琴用英语怎么读?

    R语言做小提琴图_小提琴用英语怎么读?原创黄小仙即便小仙同学决定学习R语言来提升自己作图的“逼格”的时候,心中还有有些疑虑的(嘿嘿,我这么懒,可不愿意做无用功了

  • 2014阿里巴巴web前实习生项目分析(1)

    2014阿里巴巴web前实习生项目分析(1)

  • Installous4 PC Client「建议收藏」

    Installous4 PC Client「建议收藏」Installous4PCClient下载程序请点这里写了一个IPhone上Installous4的PC端可以在电脑上搜索App以后再不用在手机上挂WIFI着下载了…哈哈哈相信越狱的同学

  • Android 获取手机分辨率「建议收藏」

    Android 获取手机分辨率「建议收藏」方法一DisplayMetricsdm=newDisplayMetrics();getWindowManager().getDefaultDisplay().getMetrics(dm);Strings=”屏幕的分辨率为:”+dm.widthPixels+”*”+dm.heightPixels;这种方法获取的屏幕高度不包含导航栏高度例如,在一部分辨率为1280×720带虚拟

  • vbs整人小代码大全

    事前准备:创建一个文件夹,后缀名为vbs,在里面编东西即可参考很多资料,如有不足请谅解文章目录vbs整人代码大全1.循环类1.1.一直说Youarefoolish!1.2.打开无数个计算器(慎用)1.3.重复说话100次1.4.不是循环但是很烦人1.5.给我按100次回车1.6.非常恶心的Alt+F42.问答类2.1.简单问答2.2.简单问答2.3.恐怖问答3.威胁类3.1.挟持回答3.2.挟持回答3.3虚惊一场结束vbs的代码完结vbs整人代码大全1.循环类1.1.一直说Youaref

  • lxml与pyquery解析html

    lxml与pyquery解析htmllxml首先来了解一下lxml,很多常用的解析html的库都用到了lxml这个库,例如BeautifulSoup、pyquery。下面我们介绍一下lxml关于html解析的3个Element。_Element_Element获取fromlxmlimportetreetext=”'<div><ul><licla…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号