求和问题总结

题目列表

问题描述

一般是给一组n个数字，给1个target, 求出k个数字的sum为target. 有变化的题目就是求closest，求个数，求组合等等

注意事项

  • 可能有重复项，注意去掉重复的组合, 除了2sum的题目最好先sort一下，这样可以方便去掉重复的项
  • sort方法枚举的时候注意不要重复，就像subsets一样

2 sum 解法

方法1 - brute force

枚举所有的k-subset, time complexity就是从N中选出k个, O(n^k)

方法2 - 先sort,再two pointer

O(NlogN + N) = O(nlogn), 要注意的是sort了之后就改变了原来的顺序

方法3 - hashmap O(n)

对于2 sum来说，其实就是对于每一个element nums[i], 在数组中找是否存在target - nums[i]

用hashmap保存访问过的value, 对每个num[i],检查hashmap中是否有target - nums[i],扫完一遍就能够得到结果。属于用空间换时间。

time complexity - O(n) space complexity - O(n)

后续题目

对于two sum的题目

  • 如果是要返回index,那么优先用hashmap的做，因为不会改变原来array的顺序
  • 如果是返回元素的value,那么可以用先sort然后two pointer的方法

对于3sum, 3sum closest, 4sum等题目，因为大部分都是根据two sum two pointer做法的延伸，所以都是要求return value

summary

two pointer

two pointer做法有利于跳过重复元素，用来计算closest, smaller等等不等于target的题目，所以优先使用

3 sum 解法

3 sum 可以退化为2 sum， 先取出一个数i, 然后在剩下的数组中找sum为target - i的就可以了。

这里要注意的是不管采取sort还是hashmap的方法，时间复杂度其实都是O(n^2). hashmap的大家都知道，排序的解释如下：

排序

sort只sort一遍 O（nlogn), 然后每一个取出一个数，再two pointer寻找的复杂度是O(n^2)

总的复杂度是 O(nlogn + n^2) = O(n^2)

3 sum closest解法

3 sum closest的解法为采取类似3 sum, 但是不要用hashmap, 用sort + two pointer的方法可以方便的找到closest

4 Sum

4 sum退化为3 sum， 可以用两个for loop内部再2 sum的方法来做 O(n^3)

###hashmap pair(似乎不对，再研究)

还有一种hashmap存pair的方法

- 首先两个for loop,将所有(i, j)的sum作为key, (i, j)作为value存在hashmap里。 ~~ ~~- 然后4 sum问题就变成了在这个hashmap里找2 sum的问题

>这种方法要注意重复的index

K sum

K sum也一步步退化，最终变为2 sum

K sum的时间复杂度是O(n^(k-1))

Reference