本文共 3057 字，大约阅读时间需要 10 分钟。
最近的文章都是有关面试最常出到的100题
许多面试好像都喜欢问这三兄弟。
给个列表，和target,返回列表中两个数加起来等于这个target的index
举例： Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].新建一个空字典，遍历一边列表，如果元素不在字典里，加进去（target-nums[i]:i），这样如果以后有元素在字典里说明我们找到了nums[j] = target-nums[i]。
时间复杂度O（n）,因为在每一层循环中查找字典都是常数时间（这个需要拓展，开一篇博客讨论hashmap和字典以及他们在python中的应用） 代码如下：if len(nums) <= 1: return False buff_dict = {} for i in range(len(nums)): if nums[i] in buff_dict: return [buff_dict[nums[i]], i] else: buff_dict[target - nums[i]] = i 比如3 sum，其问题就是给你一个长列表， nums = [-1, 0, 1, 2, -1, -4]， 再给你一个target = 0， 请输出这个列表列表中相加等于0的三个数
示例答案是这个： [ [-1, 0, 1], [-1, -1, 2] ] 因为-1+0+1 = 0， -1-1+2 = 0最慢的方法写三重循环，显然时间复杂度高了
如何减少复杂度 先排好序，然后最外层循环遍历第一个数，后面两个数怎么确定呢，j，k在每次最外层循环开始时，取i+1和len(nums)-1，就是i之后的一头一尾。nums[i]+nums[j]+nums[k]和0来比，因为数组排好序了，所以如果小于0那就是nums[j]不够大，我们把j后移一个，如果大于0那就是nums[k]太大了，我们把k前移一个。在自己手动敲代码时犯下了如下错误：
1.我想用写在for循环下的while循环里的continue结束外层的本次for循环。。但是continue就是结束它所处的领域的本次循环 2.对于只要然后重复的理解不够 3.在while中进行判断了后，直接要在if body里面写循环的变化条件呀！不要搞成死循环了呀！ 最后3sum代码如下(时间复杂度O（n2）)：res = [] nums.sort() for i in range(len(nums)-2): #考虑过的i就不用再考虑了 if i > 0 and nums[i] == nums[i-1]: continue #第二第三个数：一头一尾 l, r = i+1, len(nums)-1 while l < r: s = nums[i] + nums[l] + nums[r] if s < 0: l +=1 elif s > 0: r -= 1 #分支应该写清楚 else: res.append([nums[i], nums[l], nums[r]]) #考虑过的l就不要考虑了 while l < r and nums[l] == nums[l+1]: l += 1 while l < r and nums[r] == nums[r-1]: r -= 1 #请记住一定要写这个变化条件。。 l += 1; r -= 1 return res
给我们4个列表ABCD，从每个列表里挑1个数加起来等于0，有几种这样的组合？
Input:A = [ 1, 2]B = [-2,-1]C = [-1, 2]D = [ 0, 2]Output:2Explanation:The two tuples are:1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 02. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
这个看起来有点头疼，但是pythonic两行代码解决这个计数问题
import collectionsAB = collections.Counter(a+b for a in A for b in B)return sum(AB[-c-d] for c in C for d in D)
collections是Python内建的一个集合模块,提供了许多有用的集合类。常用类型有：
计数器（Counter）
双向队列（deque）
默认字典（defaultdict）
有序字典（OrderedDict）
可命名元组（namedtuple）
我们的4 sum II 就用到了collections模块里的Counter
Counter作为字典dict()的一个子类用来进行hashtable计数，将元素进行数量统计，计数后返回一个字典，键值为元素，值为元素个数 在我们用Counter(a+b for a in A b in B)后我们得到的是： Counter({0: 2, -1: 1, 1: 1}) A和B列表中每个元素互相相加的结果有2个0，1个-1，1个1 接下来我们只用找C D与其对应的组合就好了。 for c in C d in D是对C D列表中元素组合的遍历，把-c-d作为字典的键值，如果没存到字典里（说明这一次找到的a+b+c+d ！= 0）这一点又与普通的字典不一样，普通的字典如果你访问它没存的键值会报错 比如B = {1:2, 3:4}， 你想访问B[0]，会报错总结一下：
2 sum用的字典，将潜在的可能性一一存入，直到发现那个可以配对上的元素 3 sum，排序用的很好，先固定住第一个元素，后两个元素的移动是根据三个数的和与0的比较来进行的，大于0了，那么第三个元素太大，要往前移，小于0，第二个元素要往后移动。对于重复元素的跳过也是一大亮点 4 sum II，用的counter很巧妙，先counter出前两个列表所有和的可能性与其对应的个数，然后对于后两个列表所有和的可能性进行配对，其实思想挺像2 sum的转载地址：http://jkksi.baihongyu.com/