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;
				}
			}
		}
	}