Leetcode-16

Posted on | In |

最接近的三数之和

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

1
2
3
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

这道题让我们返回这个最接近于给定值的值，即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量diff用来记录差的绝对值，然后我们还是要先将数组排个序，然后开始遍历数组，思路跟那道三数之和很相似，都是先确定一个数，然后用两个指针left和right来滑动寻找另外两个数，每确定两个数，我们求出此三数之和，然后算和给定值的差的绝对值存在newDiff中，然后和diff比较并更新diff和结果closest即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//比较
int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

//最接近的三数之和
int threeSumClosest(int* nums, int numsSize, int target) {
	int min_diff = INT_MAX;
    if (numsSize < 3) {
        return min_diff;
    }
    
    qsort(nums, numsSize, sizeof(*nums), compare);

    for (int k = 0; k < numsSize - 2; ++k) {
    	int i = k + 1;
    	int j = numsSize - 1;
    	while (i < j) {
			int diff = nums[k] + nums[i] + nums[j] - target;
			if (abs(diff) < abs(min_diff)) {
				min_diff = diff;
			} 

			if (diff > 0) {
				j--;
			}
			else if (diff < 0) {
				i++;
			}
			else {
				return target;
			}
		}
    }

    return min_diff + target;
}

参考题目

参考答案