今天大一的夏季赛有一道很有意思的题，我认为这是一道防止AK的题，可惜数据有点水，令人惋惜，我也顺便总结说下我的做法。

题目大意

给定一个数组，试问是否存在数组中三个值，使得三个值的和为一定值。

分析

题目大意很简单，暴力的做法是三重循环，将每一个组合遍历一遍。复杂度太高不适用。

那么有什么简便的做法呢？

不如我们先从简单的开始做起。

简单版

给定一个数组，是否存在数组中的两个值，使得和为一个定值。

假设数组为 4 3 2 1 5，和为9，通过目测我们可以看出4和5可以组成一个9。

那么我们该如何降低复杂度呢？对于某个定值9而言，我们并不关心是谁和谁加起来等于9，而只关心是否存在两个值的定值为9。 如果用暴力的做法二重循环，那么虽然我们能得到所有的和的信息，但是我们也会因此得到了多余的信息。

那么如果我们只需要关注和的信息，假设我们随便取了两个数，加起来的和比定值偏小，那么我们只需要保证接下来取的值的和比刚才大即可，反之亦然。

那么我们就可以先将数组排序 变为 1 2 3 4 5

然后用两个指针指向头部和尾部，当两个指针所指的数之和偏大时，尾部指针往前移，反之依然。（这里可以想象是为什么）

用伪代码的形式表示：

Array [] = 5 , 2, 4 ,1 , 3
sort(Array)
for(i = 0 , j = Array.length -1 ;i<j ; ){
    if(Array[i]+Array[j] ==  constValue){
        We Found it
    }
    if(Array[i]+Array[j] > constValue ){
        j--;
    }
    else
        i++;
}

这样，我们在一个数组内找两个值的和为定值的复杂度就降到了O(n)

回到题意

那么三个值的和为定值该怎么写呢？其实还是在前面的基础上，对于数组内的某一个值Array[x]，你只需要在剩下的数组内找到另外两个值，使得这两个值的和为constValue - Array[x]即可，所以三个值的和的复杂度就下降到O(n²)啦！

赶紧自己试试吧=-=