【算法练习题】力扣练习题——数组（3）：最接近的三数之和

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

原题链接：https://leetcode-cn.com/problems/3sum-closest

题目分析：

一开始我顺着数组（2）的思路，很容易认为是不断地找加和结果和目标值相近的组合。如$1$的话，先找加和值为$1$，然后是$0$和$-1$。这样的话，可能就是数组（2）的基础上，删除去重的代码，然后遍历一下目标值即可。但换一个思路想想，题目只要求输出一个“最接近”的数，应该是找最小，所以直接比大小就可以了。公式为

$$diff = \min \{ diff,abs({\rm{target - }}sum)\} $$

解法一：暴力求解

目前遇到的数组题似乎都可以用暴力求解解决。原因可能是数组给定后，边界值明确，暴力求解到底还是一定的值域内进行？

暴力求解的思路就是三层循环，从内到外遍历所有组合情况，每次对组合加和值与目标值得关系进行判断。然后输出最终的比较结果即可。代码如下：

             1
            static
            int threeSumClosest(int[]nums, int target) {
 2if(nums.length<3 || nums == null)
 3return 0;
 4 5int n = nums.length;
 6int diff = 100000000, sum = 0, minsum = 10000000;
 7for(int i=0;i<n-2;i++) {
 8for(int j=i+1;j<n-1;j++) {
 9for(int k=j+1;k<n;k++) {
10                 sum = nums[i]+nums[j]+nums[k];
11if(diff>Math.abs(target-sum)) {
12                     diff = Math.abs(target-sum);
13                     minsum = sum;
14                }                
15            }        
16        }        
17    }
18return minsum;    
19 }

这次有意识地判断了不定式写入的位置（第10行）。

解法二：双指针

双指针的题目做过也不止一题了，是一种用空间复杂度换时间复杂度的方法。

但是和数组（2）的情况一样，都需要进行排序，使得能够遍历完所有的条件（我开始忘记排序，发现会遗漏情况）。

双指针是在三数中先固定最小数（最大数也是一样的），然后在剩下的数值区间内遍历。设三数和为$sum = nums[achor] + nums[pre] + nums[post]$，迭代条件是

$\left\{\begin{array}{l}{\text { sum }<\text {target, pret }++} \\ {\text { sum }>\text {target, post}--} \\ {\text { sum }=\text {target, return}}\end{array}\right.$

之后再继续内循环。

代码为

if(sum<target) pre++;
else if (sum>target) post--;
else if (sum==target) return minsum;

显然，若不排序，双指针迭代就没有意义（考虑到是有序数列（左往右递增），当然$sum$小于$target$时，将左指针右移，总和会变大）。

分析内循环的循环条件为$pre<post$，外循环的循环条件是$achor<=length-2$，这里考虑一下指针迭代会不会越界：

以左指针为例，内循环的边界条件是$pre=post-1$，此时若达成条件$pre++$，那么再进行内循环时，便满足终止条件、内循环结束，故不会数组越界。右指针迭代同理。

整体代码为：

             1
            static
            int threeSumClosest(int[] nums, int target) {
 2if(nums.length<3 || nums == null)
 3return 0;
 4 5int n = nums.length;
 6int achor = 0, pre = achor + 1, post = n - 1;
 7int diff = 100000000, sum = 0, minsum = 10000000;
 8 9    Arrays.sort(nums);
1011while(achor<=n-2) {
12while(pre<post) {
13             sum = nums[achor]+nums[pre]+nums[post];
14if(diff>Math.abs(target-sum)) {
15                 diff = Math.abs(target-sum);
16                 minsum = sum;
17            }
18if(sum<target) pre++;
19elseif (sum>target) post--;
20elseif (sum==target) return minsum;                
21        }
22         achor++;pre=achor+1;post=n-1;
23    }
24return minsum;
25 }

这里要说明的是，第14行到第17行的代码，一开始是这么写的：

diff=Math.min(diff, Math.abs(target-sum));

单这行代码的作用而言，是没错的。让我觉得棘手的是最后返回值第24行，我就无法输出最小的和了。我曾想过做$diff$和$target$之间的运算，但是后来想到（实际上程序提交后不符合...）这样的运算结果应该有两个。所以只能作罢、用一个变量来承接最小的和。

还有一个事情，在第18行到第20行，我曾作死的把判断条件改成了$diff$的正负值比较。问题是$diff$永远都是非负数。所以是自己考虑不周了。

 总结：

这道题还算是简单。

• 只要一开始审题要明确。
• 然后是搞清楚边界条件、适当推理一下
• 最后还是要搞清楚输出的是什么，我觉得一开始在变量声明时就可以注意了

原文：https://www.cnblogs.com/RicardoIsLearning/p/12034034.html