给一个包含n个整数的数组S, 找到和与给定整数target最接近的三元组,返回这三个数的和。
样例
例如S=[-1, 2, 1, -4]and target =1. 和最接近 1 的三元组是 -1 + 2 + 1 = 2.
思路:
定位头和尾两个点,在中间找最值点。然后遍历头和尾。这个方法时间代价太大,我觉得不是很好。但只能想到这里了。下面来看看九章的答案:
实在是简单了好多,仔细看看。它首先做了排序。其次,相比我的暴力算法。这个方法判断了与target的大小关系。换句话说,我的方法是无脑地搜索出目标值,而这个方法是有目的地去接近目标值。思路:
1.暴力思路:全部计算出来,然后比大小。
2.这部分有两个过程:1.计算,2.比大小。思考哪个过程可以简化?
3.比大小本身是很简单的,不用简化。那么考虑简化计算过程。
3.所谓简化计算过程就是要抛弃那些明显劣于前项的数据更新。思考 如果能够判断是否明显劣于前项?对于无序数组,不可能判断。那么先对数组排序。
4.对于有序数组如何判断是否劣于前向? 这个时候就要定义什么是优劣?
优是接近target,劣是远离target。那么只有两种结果,这个sum值小于target,或者大于target。对于小于target的值,更新要取大,反之取小。
这样反思以后,其实我的方法几乎多余,就相当于暴力算出所有可能,然后求最优。解题过程中我的困惑主要是不知道哪里去找思路。这样一来就很麻烦。