Leetcode：最接近的三数之和（双指针）

阳光穿透心脏的1/2处 2022-12-12 02:22 136阅读 0赞

**最接近的三数之和**

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

示例：
    
    输入：nums = [-1,2,1,-4], target = 1
    输出：2
    解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

> 实现思路：双指针，对于N数之和一类的问题，第一反应就应该是先排序，然后使用双指针。如果使用暴力解法，时间复杂度要O(n^3)，一般会超时，双指针的时间复杂度位O(n2)。排序后，先固定一个数nums\[k\]，然后双指针 i 和 j 从左往右依次搜索。
> 
> `int sum = nums[k] + nums[i] + nums[j];`  
> 比较 sum 和 target 的接近程度，有三种情况：  
> \`1、sum == target返回target即可
> 
> \`2、sum > target 说明 sum需要减少，由于数据已经从小到大排序，故指针 i 往右移动即可
> 
> `3`、sum < target 说明指针 j 需要往左滑动

class Solution {
        
    public:
    	int threeSumClosest(vector<int>& nums, int target) {
        
    		sort(nums.begin(), nums.end());
    		int res = 0;
    		int minData = INT_MAX;
    		for (int k = 0; k < nums.size(); ++k) {
        
    			int i = k + 1;
    			int j = nums.size() - 1;
    			while (i < j) {
        
    				int sum = nums[k] + nums[i] + nums[j];
                    if (minData > abs(target - sum)) {
        
                        minData = abs(target - sum);
                        res = sum;
                    }
    				if (target == sum) {
        
    					return target;
    				}
    				if (target > sum) {
        
    					i++;
                        continue;
    				}
    				j--;
    			}
    		}
    		return res;
    	}
    };

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1ef0d9a81af0444c8b4fc52831f1e01e.png