阿里面试：三个臭皮匠，顶个诸葛亮

作者丨爱码有道

来源丨经授权转自 公众号爱码有道

大家好，我是道哥。今天，我们来看一道阿里巴巴的面试题目，典型且有趣。问题如下：

有n个臭皮匠和1个诸葛亮，并且已知他们的智商，请判断是否存在三个臭皮匠的智商之和，刚好等于诸葛亮的智商。

很显然，这是典型的三数之和问题。为方便分析，假设n=5，臭皮匠们的智商值是{5, 3, 4, 2, 6}，诸葛亮的智商值是20. 接下来，我们循序渐进地看看各种思路。

暴力枚举

枚举法是最容易想到的办法，也就是说，把{5, 3, 4, 2, 6}中所有可能的三个数的和，都枚举计算一遍，说白了，就是暴力尝试。且看：

接下来，我们以表格的形式，更完整地呈现：

臭皮匠智商值	智商和
5	3	4	12
5	3	2	10
5	3	6	14
5	4	2	11
5	4	6	15
5	2	6	13
3	4	2	9
3	4	6	13
3	2	6	11
4	2	6	12

可见，不存在三个臭皮匠的智商之和等于20. 这就是所谓的枚举法，简单，直白，而且暴力，时间复杂度是O(N*N*N)，自然是没法通过阿里巴巴面试的。

顺便附上上述思路的代码，请注意，使用了三层循环，目标数字为a[i], a[j], a[k], 如下：

#include <iostream>
using namespace std;

bool can(int a[], int n, int ZhuGeLiang)
{
   for(int i = 0; i < n; i++)
   {
       for(int j = i + 1; j < n; j++)
       {
          for(int k = j + 1; k < n; k++)
          {
              if ( a[i] + a[j] + a[k] == ZhuGeLiang )
              {
                return true;
              }
          }
      }
   }
  
   return false;
}

int main()
{
   int a[] = {5, 3, 4, 2, 6};
   int n = sizeof(a) / sizeof(a[0]);
   int ZhuGeLiang = 20;

   if (can(a, n, ZhuGeLiang))
   {
       cout << "yes" << endl;
   }
   else
   {
       cout << "no" << endl;
   }
  
   return 0;
}

哈希查找

在暴力枚举方法中，时间复杂度不符合要求。这里的根本原因其实就是：在查找a[k]时，用的是时间复杂度为O(N)的线性查找。为什么这样说呢？且看暴力枚举的本质：

很显然，在剩余的数字中查找时，暴力枚举方法使用的是线性查找。那么，有没有更好的查找方式呢？当然有啦，用哈希查找，时间复杂度就是O(1)了：

同理，我们选定5和4后，只需要用哈希查找判断剩余数字中是否存在11即可，如下图：

那么，在整个算法中，我们对第一个a[i]和第二个数a[j]进行两层遍历，然后用20减去这两数之和，得到目标差delta，然后使用哈希查找，判断delta是否存在于剩余数字中。

由于使用了两层循环，所以整个算法的时间复杂度为O(N*N)，由于使用了哈希表，所以整个算法的空间复杂度为O(N)，基本能满足题目的要求，可以通过阿里巴巴的面试。

双指针法

在哈希查找中，我们是固定a[i]和a[j]去找delta,  其实，我们还可以固定a[i]，去找两数之和，此时，需要先进行排序，结果为：

接下来，我们先固定a[i]的值，需要找出x和y满足如下条件:

x + y = 20 - a[i]

从第一个数字开始，a[i] = 2, 所以要在剩余数字中找和为18的两个数：

尤其可见，我们把判断三数之和的问题，简化为了判断两数之和的问题。

两数之和的判断，我们使用双指针，分别指向头和尾(已经排序了)，如下：

可别忘了，我们的目标是找两数之和为18，显然，9小了，需要把左指针右移来试探：

显然，和为10，仍比18小，需要继续把左指针右移来试探，如下：

显然，和为11，仍比18小，此时没法继续右移了。到此为止，发现a[i]=2时，没法找到合适的x和y，使得三数之和为20.

接下来，就要继续遍历a[i]了，刚好a[i]=3, 接下来就是要找出x和y满足如下条件:

x + y = 17

可见，整个算法的本质就是，排序后，固定a[i], 然后通过双指针的移动来找两数之和。遍历a[i]需要O(N)次循环，双指针法需要O(N)次循环。

因此，整个算法的时间复杂度是O(N*N), 空间复杂度完全依赖于排序。以快排为例，平均空间复杂度为O(logN). 该算法能通过阿里巴巴面试。

三数之和，是常见的笔试面试题目，大家都应该重视起来。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

点分享

点点赞

点在看