16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。 
示例 1：
输入：
nums = [-1,2,1,-4], target = 1
输出：
2
解释：
与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
示例 2：
输入：
nums = [0,0,0], target = 1
输出：
0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。 
提示：
• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000

解题思路：

1. 排序数组：首先对数组进行排序，这样可以方便地使用双指针技术来寻找三元组。

2. 初始化最接近的和：使用数组的前三个数的和作为初始的最接近和。

3. 遍历数组：对于每个元素 nums[i]，使用双指针 left 和 right 分别指向 i+1 和数组末尾，寻找满足条件的三元组。

4. 计算当前和：计算当前三元组的和，如果这个和等于 target，直接返回 target。

5. 更新最接近的和：比较当前和与 target 的绝对差，更新最接近的和。

6. 调整指针：根据当前和与 target 的大小关系，移动指针以尝试更接近 target 的和。

// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {
    // 将void指针转换为int指针并解引用，返回两数之差（升序排序）
    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];
    
    // 外层循环：固定第一个数nums[i]
    for (int i = 0; i < numsSize - 2; i++) {
        // 设置双指针：left从i+1开始，right从末尾开始
        int left = i + 1;
        int right = numsSize - 1;
        
        // 内层循环：双指针遍历
        while (left < right) {
            // 计算当前三个数的和
            int currentSum = nums[i] + nums[left] + nums[right];
            
            // 如果正好等于target，直接返回（最优解）
            if (currentSum == target) {
                return currentSum;
            }
            
            // 如果当前和更接近target，更新closestSum
            if (abs(currentSum - target) < abs(closestSum - target)) {
                closestSum = currentSum;
            }
            
            // 根据当前和与target的关系移动指针
            if (currentSum < target) {
                left++;  // 和太小，左指针右移（增大和）
            } else {
                right--; // 和太大，右指针左移（减小和）
            }
        }
    }
    
    // 返回找到的最接近的和
    return closestSum;
}

实验小结

本次实验实现了寻找数组中三数之和最接近目标值的算法。通过双指针技术，我们高效地解决了这个问题。以下是主要收获：

1. 排序优化：先对数组进行排序（O(nlogn)），为双指针法创造条件，将时间复杂度优化至O(n²)。

2. 双指针技巧：固定一个数后，使用左右指针向中间遍历，有效减少了不必要的计算。

3. 实时更新：维护一个最接近的和变量，在遍历过程中不断比较更新，确保结果最优。

4. 边界处理：正确处理了数组长度为3的特殊情况，以及正负数组合的各种可能。

5. 性能验证：在测试用例中表现良好，如示例1正确返回2，示例2返回0。

实验加深了对双指针算法的理解，掌握了处理最接近值问题的方法，为类似问题（如四数之和）提供了解决思路。后续可进一步优化空间复杂度或处理更复杂变种。