小问题:求随机给定100个数中相加和为0的3个数

女票去面试，遇到个面试官提了个算法题，问题大概是“求随机给定100个数中相加和为0的3个数”，其实算法题在面试的过程中出到都是很常见的，不过这在短时间内可能很难想到。回来女票问我这个问题，她很好奇我为什么这么快能打上来？emmm，说脑子好使会不会被打，哈哈哈，今天来讲下这类题的一种套路。

1.遇到数，先排序，没错的

在遇到问题没有立马出现思路我觉得这是非常正常的事情，但是可以很明确的说，在对于数做操作的时候，有序会比无序好操作的多，毕竟有序的时候我可以采取的方式也就会更多。

2.3个数不好想，那转换成2个呢？

这其实描述性的来说，就是把复杂问题简单化。就拿这个问题来说吧，我在100个数里面取三个数的和为0可能很难处理，最笨的方法就是三层循环，o(n^3)，在实在想不出来的时候，就说这个吧。

但是转念想想，如果我们把这个问题转化为，求两个数的和等于另一个数的相反数呢？这是不是就有了点眉目了呢？

3.问题变为了，有序的100个数中，求两数和 为 x的项，是不是开始才思泉涌

具体讲下大概的算法，将100个数排序后存到数组 a 中，开始循环数组a，索引为i，然后分别取两头索引left，right对应的值a[left], a[right]的和是否等于该a[i]，在不相等时，在根据 a[left] + a[right] 和与 a[i] 的大小关系，来判断是将left+1 还是讲 right + 1 再进行比对。

4.写出大体代码

如果觉得语言描述不清，写出能代表你基本思路的代码即可，也不需要能够严格执行，最擅长php，就以php为例

$left = 0;
$right = count($a) - 1;
foreach($a as $i => $sum) {
    $_left = $left;
    $_right = $right;
    while($_left < $_right) {
        if($a[$_left] + $a[$_right] < -$a[$i]) {
            $_left ++;
            if($_left == $i) $_left ++;
        } elseif ($a[$_left] + $a[$_right] > -$a[$i]) {
            $_right --;
            if($_right == $i) $_right --;
        } else {
            return '结果相加和为0的组合之一为:...';
        }
    }
}

5.基本完成了，就该想办法优化了

暂时能想到的优化
(1) 有相同的数的话，就直接略过了，外层设置个i] 都填进去，当循环条件为 in_array(i], $has_read) 的时候 continue;

结论

这类的题目，我觉得按照大体思路这么跑，就可以，无非有序化，简单化的事情，后面这种题万变也不离其宗，无非是这几个数的三次幂啊，求几个数的积啊之类的。

你还有更好的解法吗？或者有什么有意思的题目，欢迎分享。