[Leetcode][求和问题2Sum/3Sum/4Sum/KSum]相关题目汇总/分析/总结

川长思鸟来 2022-06-10 06:23 155阅读 0赞

以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。

目前范围：Leetcode前150题

## K-SUM解题思路 ##

本总结参考：[博客][Link 1]，[Sigmainfy][]，[Ksum整理][Ksum]

**求和问题描述(K sum problem)：**

K sum的求和问题一般是这样子描述的：给你一组N个数字(比如 vector num), 然后给你一个目标常数(比如 int target) ，我们的目的是在这一堆数里面找到K个数字，使得这K个数字的和等于target。

**K Sum求解方法, 适用2Sum, 3Sum, 4Sum：**

方法一： 暴力，就是枚举所有的K-subset, 那么这样的复杂度就是 从N选出K个，复杂度是O(N^K)，**显然不会考察这种方法**

方法二： 双指针，这个算法可以考虑最简单的case, 2sum，这是个经典问题，方法就是先排序，然后利用头尾指针找到两个数使得他们的和等于target，其他Ksum都是同样的思路，只不过要固定前K-2个（利用循环）**该方法最容易理解**

方法三：哈希表  
将可能的解存储在hash表中，在数据量很大的时候，去重才能维持很好的效率，不然可能超时。**效率高**

## 题目汇总 ##

*  [2Sum][]
 *  [3Sum][]
 *  [3Sum Closest][]
 *  [4Sum][]

## 总结 ##

哈希表和双指针都是重要的思路。

双指针方法大多需要排序，python中的排序复杂度[参考][Link 2]

时间复杂度对于上界O来说，永远是只写最高的，O(n log n)+ O（n^2）= O（n^2）

[Link 1]: http://wulc.me/2016/03/08/LeetCode%20%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A%28167,%201,%2015,%2016,%2018%29--%E5%8F%8C%E6%8C%87%E9%92%88%E8%A7%A3%E5%86%B3ksum%E9%97%AE%E9%A2%98/
[Sigmainfy]: https://www.sigmainfy.com/blog/summary-of-ksum-problems.html
[Ksum]: https://www.hrwhisper.me/leetcode-2-sum-3-sum-4-sum-3-sum-closest-k-sum/
[2Sum]: http://blog.csdn.net/qqxx6661/article/details/74279306
[3Sum]: http://blog.csdn.net/qqxx6661/article/details/77104862
[3Sum Closest]: http://blog.csdn.net/qqxx6661/article/details/77104867
[4Sum]: http://blog.csdn.net/qqxx6661/article/details/77104868
[Link 2]: http://www.orangecube.net/python-time-complexity