第十六题：最接近的三数之和

2024-09-06 14:12

文章标签 三数第十六接近

本文主要是介绍第十六题：最接近的三数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

示例：

输入：nums = [-1, 2, 1, -4], target = 1
输出：2
解释：与 target 最接近的和为 2 (-1 + 2 + 1 = 2)。

注意：

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

实现思路

先对数组进行排序，然后遍历数组中的每个元素作为三元组的第一个元素，对于每个元素使用双指针法在剩下的数组中寻找另外两个数，使得三者之和最接近目标值。为了避免重复计算，可以跳过重复的元素。

算法实现

C

#include <stdio.h>
int cmp(const void *a, const void *b) { return (*(int*)a - *(int*)b); }
int threeSumClosest(int* nums, int numsSize, int target) {qsort(nums, numsSize, sizeof(int), cmp);int closestSum = nums[0] + nums[1] + nums[2];for (int i = 0; i < numsSize - 2; ++i) {int left = i + 1, right = numsSize - 1;while (left < right) {int currentSum = nums[i] + nums[left] + nums[right];if (abs(target - currentSum) < abs(target - closestSum)) {closestSum = currentSum;}if (currentSum < target) {++left;} else if (currentSum > target) {--right;} else {return target;}}}return closestSum;
}

Python

def threeSumClosest(nums, target):nums.sort()closest_sum = sum(nums[:3])for i in range(len(nums) - 2):left, right = i + 1, len(nums) - 1while left < right:current_sum = nums[i] + nums[left] + nums[right]if abs(target - current_sum) < abs(target - closest_sum):closest_sum = current_sumif current_sum < target:left += 1elif current_sum > target:right -= 1else:return targetreturn closest_sum

Java

import java.util.Arrays;
public class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int closestSum = nums[0] + nums[1] + nums[2];for (int i = 0; i < nums.length - 2; ++i) {int left = i + 1, right = nums.length - 1;while (left < right) {int currentSum = nums[i] + nums[left] + nums[right];if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {closestSum = currentSum;}if (currentSum < target) {++left;} else if (currentSum > target) {--right;} else {return target;}}}return closestSum;}
}