LeetCode_双指针_中等_16.最接近的三数之和

野性酷女 2023-10-06 18:04 46阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

**提示：**  
3 <= nums.length <= 103  
\-103 <= nums\[i\] <= 103  
\-104 <= target <= 104

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

## 2.思路 ##

（1）暴力穷举法  
先对数组进行升序排序，然后使用三层 for 循环来依次遍历出所有的组合，并且使用变量 dif 来保存当前三个整数之和与 target 之间的差值的最小值，循环结束后，dif 与 target 之和即为要找的三个数之和。值得注意的是，由于数组经过升序排序后，如果第一层循环中的当前相邻的三个整数之和与 target 之间的差值大于或等于 dif，那么则说明后面的任意三个整数之和与 target 的差值只会更大（因为数组是递增的），所以此时可以直接退出循环。

（2）排序 & 双指针

*  先对数组进行升序排序，并且取 res = nums\[0\] + nums\[1\] + nums\[2\] 来作为初始对比组；
 *  遍历数组中的第1 ~ n - 2个元素 nums\[i\]（0 <= i < nums.length - 2）；
 *  对于每一个 nums\[i\]，定义两个指针 j 和 k，其中 j 指针指向 i + 1 处，k 指针指向 nums.length - 1 处，判断 target 与sum=nums\[i\] + nums\[j\] + nums\[k\]之间的差值是否比上一次的差值更小，如果是则更新 res = sum；
 *  判断 target 与 sum 之间的关系，并根据结果来选择要移动的指针，从而得到更加合适的一组整数。值得注意的是如果 target = sum，则直接返回结果。

相关题目：  
[LeetCode\_双指针\_哈希表\_简单\_1.两数之和][LeetCode_1.]  
[LeetCode\_双指针\_中等\_15.三数之和][LeetCode_15.]  
[LeetCode\_双指针\_中等\_18.四数之和][LeetCode_18.]  
[LeetCode\_双指针\_中等\_167.两数之和 II - 输入有序数组][LeetCode_167._ II -]  
[LeetCode\_哈希表\_中等\_454.四数相加 II][LeetCode_454._ II]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
    	public int threeSumClosest(int[] nums, int target) {
        
    	    Arrays.sort(nums);
    	    //将三个整数之和与target之间的差值的初始值设为int可以表示的最大值
    	    int dif = Integer.MAX_VALUE;
    	    int temp;
    	    for (int i = 0; i < nums.length - 2; i++) {
        
    	        for (int j = i + 1; j < nums.length - 1; j++) {
        
    	            for (int k = j + 1; k < nums.length; k++) {
        
    	                temp = nums[i] + nums[j] + nums[k] - target;
    	                if (Math.abs(temp) < Math.abs(dif)) {
        
    	                    dif = temp;
    	                }
    	            }
    	        }
    	        if (Math.abs(dif) <= nums[i] + nums[i + 1] + nums[i + 2] - target) {
        
    	            break;
    	        }
    	    }
    	    return dif + target;
    	}
    }

//思路2————排序 & 双指针
    class Solution {
        
    	public int threeSumClosest(int[] nums, int target) {
        
    	    //对数组进行排序
    	    Arrays.sort(nums);
    	    //排序之后，最前面的三个元素之和最小
    	    int res = nums[0] + nums[1] + nums[2];
    	    for (int i = 0; i < nums.length - 2; i++) {
        
    	        //定义双指针
    	        int j = i + 1, k = nums.length - 1;
    	        while (j < k) {
        
    	            int sum = nums[i] + nums[j] + nums[k];
    	            //如果上一组的三个整数之和与 target 之间的差值大于本组的，则更新 res
    	            if (Math.abs(target - sum) < Math.abs(target - res)) {
        
    	                res = sum;
    	            }
    	            if (sum == target) {
        
    	                return res;
    	            } else if (sum < target) {
        
    	                j++;
    	            }
    	            else {
        
    	                k--;
    	            }
    	        }
    	    }
    	    return res;
    	}
    }

[LeetCode_1.]: https://blog.csdn.net/weixin_43004044/article/details/118055101
[LeetCode_15.]: https://blog.csdn.net/weixin_43004044/article/details/118107655
[LeetCode_18.]: https://blog.csdn.net/weixin_43004044/article/details/118164049
[LeetCode_167._ II -]: https://blog.csdn.net/weixin_43004044/article/details/129296040
[LeetCode_454._ II]: https://blog.csdn.net/weixin_43004044/article/details/125439346