本文共 750 字，大约阅读时间需要 2 分钟。

1,15,16,18

转载自： 方法一：暴力搜索法 时间复杂度O（n^k） 方法二：排序 2sum:采用快速排序法，排序后采用前后指针。当和为target，则找到答案返回；当和大于target，时，右指针左移；当和小于target时，左指针右移。循环上述过程，若找到则返回，否则直至left=right说明没有解。最后在原数组中找到符合要求的两个数的位置即可。 时间复杂度为O（nlogn） 3sum:采用快速排序法只排一次，每次取一个数x，问题转化为target-x的2sum问题，前后指针法时间复杂度为O(n) 时间复杂度为O（n^2） 4sum:采用快速排序法只排一次，每次取一个数x，问题转化为target-x的3sum问题 时间复杂度为O（n^3） …… ksum:时间复杂度为O（n^(k-1)) 优化：ksum每次取一个数x,只需要对x后的数进行target-x的(k-1)sum问题 除重问题：可以利用set的性质 方法三：哈希 字典{元素：索引} 2sum:如果target-元素在哈希表则返回，不在则将元素添加至哈希表 时间复杂度为O（n） 3sum:每次取一个数x，问题转化为target-x的2sum问题 时间复杂度为O（n^2） 4sum:每次取一个数x，问题转化为target-x的3sum问题 时间复杂度为O（n^3） 除重问题：无论重复元素有多少个，字典中只存放一个的索引 此时哈希表的优势就体现出来，我们可以遍历所有可能的pair，把所有的pair存在dict中，key=a+b, value是一个list，每个元素为(a, b)。时间复杂度为O(n^2)。 但是，我们不可以直接利用pair当作2sum问题，因为这样会有重复的，需要将查找到的two pairs去重