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

admin
学习
2024-02-28
43热度
0评论

题目来源：LeetCode第十六题

1.题目描述

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1

输出：2

解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10⁴ <= target <= 10⁴

2.解题思路

解法一：暴力法

描述：遍历数组中的每三个数字的所有可能组合，计算它们的和，并与目标值 target 进行比较，记录与 target 最接近的和。
时间复杂度：O(n^3)。三层循环。
空间复杂度：O(1)。
参考代码：

java版：

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        // 初始化最接近的和为前三个数的和
        int closestSum = nums[0] + nums[1] + nums[2];
        // 遍历数组中的每三个数字的所有可能组合
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    // 当前三个数字的和
                    int currentSum = nums[i] + nums[j] + nums[k];
                    // 如果当前和与目标值更接近，则更新最接近的和
                    if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                        closestSum = currentSum;
                    }
                }
            }
        }

        return closestSum;
    }
}

C++版：

class Solution {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		int n = nums.size();
		// 初始化最接近的和为前三个数的和
		int closestSum = nums[0] + nums[1] + nums[2];
		// 遍历数组中的每三个数字的所有可能组合
		for (int i = 0; i < n - 2; i++) {
			for (int j = i + 1; j < n - 1; j++) {
				for (int k = j + 1; k < n; k++) {
					// 当前三个数字的和
					int currentSum = nums[i] + nums[j] + nums[k];
					// 如果当前和与目标值更接近，则更新最接近的和
					if (abs(target - currentSum) < abs(target - closestSum)) {
						closestSum = currentSum;
					}
				}
			}
		}

		return closestSum;
	}
};

C版：

// 计算三数之和最接近target的函数
int threeSumClosest(int* nums, int numsSize, int target) {
	int closestSum = nums[0] + nums[1] + nums[2]; // 初始化最接近的和为前三个数的和
	// 遍历所有可能的三个数字的组合
	for (int i = 0; i < numsSize - 2; i++) {
		for (int j = i + 1; j < numsSize - 1; j++) {
			for (int k = j + 1; k < numsSize; k++) {
				int currentSum = nums[i] + nums[j] + nums[k]; // 当前三个数字的和
				// 如果当前和与目标值更接近，则更新最接近的和
				if (abs(target - currentSum) < abs(target - closestSum)) {
					closestSum = currentSum;
				}
			}
		}
	}
	// 返回和与目标值最接近的和
	return closestSum;
}

解法二：排序+双指针

描述：首先对输入数组进行排序。这是实现双指针策略的前提，选择一个初始的“最接近的和”作为比较基准，使用一个循环遍历排序后的数组，每次循环中，固定一个元素作为三数之和中的第一个数。在每次遍历的过程中，使用两个指针分别指向当前元素之后的第一个元素（左指针）和数组的最后一个元素（右指针）。计算当前三个数的和，并与目标值进行比较，在遍历和移动双指针的过程中，如果找到一个和更接近目标值，则更新“最接近的和”。遍历完成后，返回找到的最接近目标值的和。
时间复杂度：O(N2)。其中 N是数组 nums的长度。排序的时间复杂度是 O(nlogn)，其中 n 是数组的长度。整个遍历加双指针搜索的总时间复杂度是O(n2)。O(nlogn+n2)，可以简化为O(n2)
空间复杂度：O(logn)（递归栈的空间）。
参考代码：

java版：

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        // 对数组进行排序
        Arrays.sort(nums);
        // 初始化最接近的和为前三个数的和（或任意三个数的和）
        int closestSum = nums[0] + nums[1] + nums[2];
        // 遍历数组
        for (int i = 0; i < n - 2; i++) {
            // 使用双指针
            int left = i + 1;
            int right = n - 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 currentSum;
                }
            }
        }
        return closestSum;
    }
}

C++版：

class Solution {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		int n = nums.size();
		// 对数组进行排序
		sort(nums.begin(), nums.end());
		// 初始化最接近的和为前三个数的和（或任意三个数的和）
		int closetSum = nums[0] + nums[1] + nums[2];
		// 遍历数组
		for (int i = 0; i < n - 2; i++) {
			// 使用双指针
			int left = i + 1;
			int right = n - 1;

			while (left < right) {
				int currentSum = nums[i] + nums[left] + nums[right];
				// 如果当前和更接近于目标值，则更新最接近的和
				if (abs(target - currentSum) < abs(target - closetSum)) {
					closetSum = currentSum;
				}
				// 根据和与目标值的比较结果移动指针
				if (currentSum < target) {
					// 增加和的值
					left++;
				}
				else if (currentSum > target) {
					// 减少和的值
					right--;
				}
				else {
					// 如果和等于目标值，直接返回该和
					return currentSum;
				}
			}
		}
		return closetSum;
	}
};

C版：

// 比较函数，用于qsort
int compare(const void* a, const void* b) {
	return (*(int*)a - *(int*)b);
}

// 计算三数之和最接近target的函数
int threeSumClosest(int* nums, int numsSize, int target) {
	// 对数组进行排序
	qsort(nums, numsSize, sizeof(int), compare);

	// 初始化最接近的和为前三个数的和（或任意三个数的和）
	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 currentSum;
			}
		}
	}

	// 返回最接近目标值的和
	return closestSum;
}