LeetCode最接近的三数之和——C

﹏ヽ暗。殇╰゛Y 2021-10-30 00:16 165阅读 0赞

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/3sum-closest

## 题目描述 ##

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

例如，给定数组 nums = \[-1，2，1，-4\], 和 target = 1.  
与 target 最接近的三个数的和为 2 (-1 + 2 + 1 = 2)

## 题解 ##

和上一道题类似，只不过上一道题的目标值为0罢了，基本原理一样。  
**双指针求解**  
1、先排序，从小到大排序  
2、选取一个数为标准，另外两个数均在这个数后面（一个i+1、一个末尾），然后对比这个标准。  
3、当left<right时循环，求和三种情况

(1)sum<target		left++
    (2)sum>target		right--
    (3)sum==target		符合条件记录三数之和

4、为了节约内存，需要进行去重。

## 代码 ##

void quickSort(int* nums, int first, int end) {					//快速排序 
    	int temp, l, r;
    	if (first >= end) {
    		return;
    	}
    	temp = nums[first];
    	l = first;
    	r = end;
    	while (l < r) {
    		while (l < r && nums[r] >= temp) {
    			r--;
    		}
    		if (l < r) {
    			nums[l] = nums[r];
    		}
    		while (l < r && nums[l] <= temp) {
    			l++;
    		}
    		if (l < r) {
    			nums[r] = nums[l];
    		}
    	}
    	nums[l] = temp;
    	quickSort(nums, first, l - 1);
    	quickSort(nums, l + 1, end);
    }
    
    int threeSumClosest(int* nums, int numsSize, int target) {
    	int i = 0;													//当前数值下标
    	int res = nums[0] + nums[1] + nums[2];						//和,初始化
    
    	if (numsSize < 3 || nums == NULL) {
    		return NULL;
    	}
    
    	quickSort(nums, 0, numsSize - 1);                           //排序
    
    	for (i = 0; i <= numsSize - 3; i++) {
    		int left = i + 1;										//左指针
    		int right = numsSize - 1;								//右指针
    		if (i > 0 && nums[i] == nums[i - 1]) {					//去重
    			continue;
    		}
    		while (left < right) {
    			int sum = nums[i] + nums[left] + nums[right];
    			if (abs(sum - target) < abs(res - target)) {		//取最近的和 
    				res = sum;
    			}
    			if (sum > target) {
    				while (left < right && nums[right] == nums[right - 1]) {
    					right--;
    				}
    				right--;
    			}
    			else if (sum < target) {
    				while (left < right && nums[left] == nums[left + 1]) {
    					left++;
    				}
    				left++;
    			}
    			else {
    				return sum;
    			}
    		}
    	}
    	return res;
    }

## 调试 ##

#include<stdio.h> 
    #include<math.h>
    
    int main() {
    	int num[] = { 1,1,1,1 };
    	int* nums = (int*)num;
    	int numsSize = sizeof(num) / sizeof(int);
    	int target = 100;
    	int sum = threeSumClosest(nums, numsSize, target);
    	printf("%d\n", sum);
    	return 0;
    }

## 结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190818141758876.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211029/171b6e94c6d3403b80b512bbc37e4881.png