原文发表于：
两数之和(two sum)是很典型的笔试面试题目，也是leetcode的第一题。为了便于叙述，我把原问题简化一下：
给定数组a[N], 判断是否存在两个元素的和为k.
针对每一个a[i], 我们再次遍历数组a[N], 然后判断a[i]+a[j]的值是否等于k, 其中 j > i. 这是最直观最暴力的解法。时间复杂度是O(N*N), 空间复杂度是O(1).
如果这样解答，虽然正确，但肯定是无法通过笔试面试的。
分析一下，针对每一个a[i], 在找合理a[j]的过程中，用的是线性查找，显然就中招了，为什么不用哈希查找呢？
我们来对算法1进行改进：
针对每一个a[i]，需要在数组a[N]中查找k-a[i]的值，而最快的查找是哈希查找(时间复杂度是O(1)). 所以，整体的时间复杂度是O(N). 由于用到了哈希表，所以空间复杂度也是O(N).
这种以空间换时间的做法，是经常用到的。这种解法是满足笔试面试要求的。
代码实现如下(结果是满足条件的值的下标)：
func twoSum(nums []int, target int) []int { var result []int m := make(map[int]int) lenN := len(nums) for i, v := range nums { m[v] = i } for i := 0; i < lenN; i++ { if j, ok := m[target - nums[i]]; ok && i < j { result = append(result, i, j) } } return result }测试结果如下：
如上代码，虽然是单层循环，但循环用了2次，实际上还可以继续优化，统一到一个循环中。这个优化不难，故不再赘述。
如果要求空间复杂度为O(logN)，时间复杂度尽可能低，那该怎么办呢？
可以考虑快速排序和双指针法，具体如下：
步骤一：快速排序
步骤二：双指针夹逼，如下：
循环条件是while(left < high):
if a[left]+a[right]刚好等于k, 那么就找到了和为k的两个数。
if a[left]+a[right]比k小, 则left++, 用更大的数来尝试。
if a[left]+a[right]比k大, 则righ--, 用更小的数来尝试。
这种解法也挺巧妙的，整体的时间复杂度为O(N*logN), 空间复杂度为O(logN), 也是可以满足笔试面试要求的。
上面讨论了两数之和，那么三数之和的问题怎么处理呢？显然，也是3种方法：
算法1：三层循环(这种暴力解法无法通过笔试面试)
时间复杂度为O(N*N*N), 空间复杂度为O(1).
算法2：双循环+哈希表
时间复杂度为O(N*N), 空间复杂度为O(N).
算法3：快排+双指针
时间复杂度为O(N*N), 空间复杂度为O(logN).
阿里、腾讯、头条的面试官真的好喜欢leetcode. 祝拿到心仪的offer.
涛歌依旧 认证博客专家 排名第一 点链接学人工智能 公众号免费领资料 ❤️零基础入门进阶人工智能 ❤️欢迎关注涛哥公众号，免费领海量学习资料。涛哥：毕业后就职于华为和腾讯。微信：ai_taogeyijiu
