LeetCode 16. 最接近的三数之和 - C语言实现题目描述给定一个包括 n 个整数的数组nums和一个目标值target找出nums中的三个整数使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。解题思路排序先对数组排序固定一个数 双指针遍历每个元素作为第一个数用双指针在其右侧找另外两个数记录最接近的和每次计算三数之和更新最接近target的结果C语言代码实现#includestdio.h#includestdlib.h#includelimits.h// 比较函数用于qsort排序intcmp(constvoid*a,constvoid*b){return(*(int*)a-*(int*)b);}intthreeSumClosest(int*nums,intnumsSize,inttarget){// 先对数组排序qsort(nums,numsSize,sizeof(int),cmp);// 初始化最接近的和为前三个数的和intclosestSumnumsnumsnums;// 遍历第一个数for(inti0;inumsSize-2;i){intlefti1;intrightnumsSize-1;while(leftright){intsumnums[i]nums[left]nums[right];// 如果正好等于target直接返回if(sumtarget){returnsum;}// 更新最接近的和if(abs(sum-target)abs(closestSum-target)){closestSumsum;}// 根据sum与target的大小关系移动指针if(sumtarget){left;// 需要更大的和}else{right--;// 需要更小的和}}}returnclosestSum;}// 测试代码intmain(){intnums1[]{-1,2,1,-4};inttarget11;intresult1threeSumClosest(nums1,4,target1);printf(输入: [-1, 2, 1, -4], target 1\n);printf(输出: %d\n\n,result1);// 期望: 2 (-1212)intnums2[]{0,0,0};inttarget21;intresult2threeSumClosest(nums2,3,target2);printf(输入: [0, 0, 0], target 1\n);printf(输出: %d\n\n,result2);// 期望: 0intnums3[]{1,1,1,0};inttarget3-100;intresult3threeSumClosest(nums3,4,target3);printf(输入: [1, 1, 1, 0], target -100\n);printf(输出: %d\n,result3);// 期望: 2return0;}复杂度分析复杂度说明时间复杂度O(n²)排序O(nlogn) 双指针遍历O(n²)空间复杂度O(1)只使用了常数额外空间不算排序的栈空间执行流程图解排序后: [-4, -1, 1, 2], target 1 i0, nums[i]-4: left1, right3: sum-4(-1)2-3 (1, left) left2, right3: sum-412-1 (1, left) left3, right3: break i1, nums[i]-1: left2, right3: sum-1122 (1, right--) left2, right2: break 最接近: 2 (|2-1|1 |-1-1|2)关键优化点提前退出当sum target时直接返回因为已经是最优解双指针移动策略根据当前和与目标的比较决定指针移动方向排序后去重本题不需要显式去重因为只需要一个答案LeetCode 16. 最接近的三数之和 - C语言实现题目描述给定一个包括 n 个整数的数组nums和一个目标值target找出nums中的三个整数使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。解题思路排序先对数组排序固定一个数 双指针遍历每个元素作为第一个数用双指针在其右侧找另外两个数记录最接近的和每次计算三数之和更新最接近target的结果C语言代码实现#includestdio.h#includestdlib.h#includelimits.h// 比较函数用于qsort排序intcmp(constvoid*a,constvoid*b){return(*(int*)a-*(int*)b);}intthreeSumClosest(int*nums,intnumsSize,inttarget){// 先对数组排序qsort(nums,numsSize,sizeof(int),cmp);// 初始化最接近的和为前三个数的和intclosestSumnumsnumsnums;// 遍历第一个数for(inti0;inumsSize-2;i){intlefti1;intrightnumsSize-1;while(leftright){intsumnums[i]nums[left]nums[right];// 如果正好等于target直接返回if(sumtarget){returnsum;}// 更新最接近的和if(abs(sum-target)abs(closestSum-target)){closestSumsum;}// 根据sum与target的大小关系移动指针if(sumtarget){left;// 需要更大的和}else{right--;// 需要更小的和}}}returnclosestSum;}// 测试代码intmain(){intnums1[]{-1,2,1,-4};inttarget11;intresult1threeSumClosest(nums1,4,target1);printf(输入: [-1, 2, 1, -4], target 1\n);printf(输出: %d\n\n,result1);// 期望: 2 (-1212)intnums2[]{0,0,0};inttarget21;intresult2threeSumClosest(nums2,3,target2);printf(输入: [0, 0, 0], target 1\n);printf(输出: %d\n\n,result2);// 期望: 0intnums3[]{1,1,1,0};inttarget3-100;intresult3threeSumClosest(nums3,4,target3);printf(输入: [1, 1, 1, 0], target -100\n);printf(输出: %d\n,result3);// 期望: 2return0;}复杂度分析复杂度说明时间复杂度O(n²)排序O(nlogn) 双指针遍历O(n²)空间复杂度O(1)只使用了常数额外空间不算排序的栈空间执行流程图解排序后: [-4, -1, 1, 2], target 1 i0, nums[i]-4: left1, right3: sum-4(-1)2-3 (1, left) left2, right3: sum-412-1 (1, left) left3, right3: break i1, nums[i]-1: left2, right3: sum-1122 (1, right--) left2, right2: break 最接近: 2 (|2-1|1 |-1-1|2)关键优化点提前退出当sum target时直接返回因为已经是最优解双指针移动策略根据当前和与目标的比较决定指针移动方向排序后去重本题不需要显式去重因为只需要一个答案