博客

#3Sum Closest

##题目

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

##分析

求三个数的和的时候，我们可以先确定一个选定的数，然后通过另外两个数的和来确定答案，我们先将数组排好序，设定两个下标，一个是选定的下标的下一个，另外一个是数组的最后一个，将三个数相加，有一下三种情况：

1. 和==target，直接返回。
2. 和 < target，记录当前的和并比较，然后小的下标往前移动。
3. 和 > target。记录当前的和并比较，然后大的下标往前移动。
   
   最后通过记录的和与target相差最小的值，返回。

##源码

int threeSumClosest(int* nums, int numsSize, int target) {
	//对数组进行排序
	for(int i = 0; i < numsSize; i++) {
		for(int j = 0; j < numsSize - i - 1; j++) {
			if(nums[j] > nums[j+1]) {
				int temp = nums[j];
				nums[j] = nums[j+1];
				nums[j+1] = temp;
			}
		}
	}
	int tag = 9999;
	int flat = -1;
	//思路是先选定一个下标，通过另外两个数字的和确定最小的。从两边开始
    for(int i = 0 ; i < numsSize; i++) {
    	int begin = i + 1;
    	int end =  numsSize - 1;
    	int left = target - nums[i];
    	
    	while(begin < end) {
    		int sum = nums[begin] + nums[end];
    		if(sum < left) {
    			begin++;
    			if(abs(left - sum) < tag) {
    				tag = abs(left - sum);
    				flat = 0;
    			}
    		} else if(sum > left) {
    			end--;
    			if(abs(left - sum) < tag) {
    				tag = abs(left - sum);
    				flat = 1;
    			}
    		} else {
    			return (nums[i] + nums[begin] + nums[end]);
    		}
    	}
    }
    if(flat == 0) {
    	return target-tag;
    } else {
    	return target+tag;
    }
}

更多技术博客

：

https://vilin.club/