企业官网建设流程全解析

以下是 LeetCode 第 16 题「最接近的三数之和」的 Java 实现，采用 排序 + 双指针 的经典解法：

解题思路

1. 排序：先对数组排序，便于使用双指针
2. 固定一个数：遍历数组，固定 `nums[i]` 作为第一个数
3. 双指针查找：在 `i` 右侧使用双指针 `left` 和 `right` 寻找另外两个数，使三数之和最接近 `target`
4. 移动策略：
- 若 `sum < target`，`left++`（需要更大的和）
- 若 `sum > target`，`right--`（需要更小的和）
- 若 `sum == target`，直接返回（不可能更接近了）
5. 更新答案：每次计算差值绝对值，保留最接近的和

Java 代码

```java
import java.util.Arrays;

class Solution {
public int threeSumClosest(int[] nums, int target) {
// 先排序，便于双指针操作
Arrays.sort(nums);

int n = nums.length;
// 初始化答案为前三个数之和
int closestSum = nums[0] + nums[1] + nums[2];

// 固定第一个数 nums[i]
for (int i = 0; i < n - 2; i++) {
// 可选：跳过重复元素，减少不必要的计算
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}

int left = i + 1; // 左指针
int right = n - 1; // 右指针

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];

// 如果恰好等于 target，直接返回（不可能更接近了）
if (sum == target) {
return sum;
}

// 更新最接近的和：比较当前差值与历史最小差值
if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
}

// 根据和与 target 的大小关系移动指针
if (sum < target) {
left++; // 和太小，左指针右移以增大和
} else {
right--; // 和太大，右指针左移以减小和
}
}
}

return closestSum;
}
}
```

复杂度分析

指标 复杂度 说明
时间复杂度 O(n²) 排序 O(n log n) + 双指针遍历 O(n²)
空间复杂度 O(1) 只使用了常数额外空间（排序是原地排序）

示例验证

- 输入：`nums = [-1, 2, 1, -4]`, `target = 1`
- 排序后：`[-4, -1, 1, 2]`
- 过程：
- i=0, nums[i]=-4: left=1(-1), right=3(2) → sum=-3, 差值=4
- i=1, nums[i]=-1: left=2(1), right=3(2) → sum=2, 差值=1（更新答案）
- 输出：`2`

优化版本（带剪枝）

```java
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int closestSum = nums[0] + nums[1] + nums[2];

// 边界剪枝：如果最小三数之和已 >= target，后面的只会更大
if (closestSum >= target) return closestSum;

// 边界剪枝：如果最大三数之和已 <= target，后面的只会更小
int maxSum = nums[n-1] + nums[n-2] + nums[n-3];
if (maxSum <= target) return maxSum;

for (int i = 0; i < n - 2; i++) {
int left = i + 1, right = n - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];

if (sum == target) return sum;

if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
}

if (sum < target) {
left++;
} else {
right--;
}
}
}
return closestSum;
}
}
```

带剪枝的版本在某些测试用例下可以减少运行时间，但时间复杂度仍为 O(n²)。