leetcode16.最接近的三数之和

leetcode16.最接近的三数之和

二月 21, 2020

leetcode16.最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

和15题的解法差不多，只不过少了很多判断条件，因为这次不用知道是哪些数，只需要求和就行，在 i+1 和末尾放两个指针，满足条件的时候指针左移或者右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int threeSumClosest(int[] nums, int target) {
     int result=0;int left=0,right=0,sum=0;
        Arrays.sort(nums);
        result=nums[0]+nums[1]+nums[2];
        //这里要给result赋值，但是又不能为最大值或者最小值，因为会越界
        for(int i=0;i<nums.length;i++) {
        	left=i+1;
        	right=nums.length-1;
        	while(left<right) {
            	sum=nums[i]+nums[left]+nums[right];
            	if(Math.abs(sum-target)<Math.abs(result-target)) {
            		result=sum;
            	}
            	if(sum>target)right--;
            	else if(sum<target)left++;
            	else return sum;
        	}
        }
        return result;   
    }

leetcode 11/100