【Leetcode】【求和问题2Sum 3Sum 4Sum KSum】相关题目汇总 分析 总结

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

目前范围:Leetcode前150题

K-SUM解题思路

本总结参考:博客SigmainfyKsum整理

求和问题描述(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表中,在数据量很大的时候,去重才能维持很好的效率,不然可能超时。效率高

题目汇总

总结

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

双指针方法大多需要排序,python中的排序复杂度参考

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