K Sum(2 Sum,3 Sum,4 Sum,3-Sum Closest)
算是经典算法问题了。这里主要针对只存在一个解或者只需要求一个解的情况描述一下解题思路。若需要找到所有可能解,方法需要略作调整。如有问题,欢迎指正。
2 sum:
如果已排序,可直接用夹逼法,即两指针从头尾向中间移动,使和靠近target。时间复杂度为O(n)。
若未排序,因为除非有特别限制,比较排序的时间复杂度为O(nlgn)。此时用hash更为合适,可以达到O(n)的时间复杂度。此方法实际上对已排序数组也实用。步骤如下:
每一个数a在放入hash表前,判断目标target-a是否在hash 表内,如果在,则找到解。否则将a放入表中。
这种方法比先完整构建hash表再检查少扫描一遍数组。
k sum(k>=3):
一个通用的方法就是先排序,然后依次固定序列中的一个数,对其后的所有数递归做k-1 sum。这样的时间复杂度是O(nk-1)。
4 Sum:
除了上面k sum的方法外,另一个方法是降到k/2=2 sum。方法大致如下:
把原数组的元素两两求和(非相同序号,个数为O(n2)),记录在一个结构体单元内,其中包含此和以及对应两元素的原始index,时空复杂度均为O(n2)
以两两和为关键字进行排序,时间复杂度O(n2logn)
再用夹逼求2 sum,若两值包含某相同下标(最多四次比较)则跳过,指针按上次方向继续移动。复杂度O(n2)。
所以总的复杂度为O(n2logn)。同样,若最后的夹逼若改为hash,可到O(n2)。
理论上讲,这种方法也许也可以推广到更高价k=2m sum,但是这是一种空间换时间的方法,空间增长很快,而且因为涉及判断下标是否重复,逻辑真的有点复杂。。。
3-Sum Closest
与3 sum类似,但固定一个数后,用夹逼时,记录两个数的和与当前target的差。时间复杂度仍然为O(n2)。
若需要找到所有可能解且元素有重复时,使用上述通用方法,在做递归的过程中,若当前求k sum,重复元素个数为m,则根据和中包含0~min(k,m)个此元素继续递归即可。
最新文章
- 使用phantomjs实现highcharts等报表通过邮件发送(本文仅提供完整解决方案和实现思路,完全照搬不去整理代码无法马上得到效果)
- SQL基础分类
- iOS开源项目教程大合集
- Android 监听ContentProvider的数据改变
- 在备份和导入mysql数据库遇到的几个问题
- AppWidgetProvider生命周期
- Docker之配置Centos_ssh
- myeclipse复制项目
- AIO5打印样式函数说明
- [LeetCode] Minimum Distance Between BST Nodes 二叉搜索树中结点的最小距离
- python continue的应用
- [NOIP2017] 宝藏 【树形DP】【状压DP】
- HaProxy 负载均衡集群
- [Vuejs] 组件 v-if 和 v-show 切换时生命周期钩子的执行
- PHP扩展迁移为PHP7扩展兼容性问题记录
- Java 单例模式的常见应用场景
- 初识Mybatis框架
- 〖Linux〗(2013.08.02)使用ctag+cscope查看Android源代码
- Oracle案例02——ORA-12034: ";SCOTT";.";USER_TABLE"; 上的实体化视图日志比上次刷新后的内容新
- Webpack笔记(三)——一款破产版脚手架的开发
热门文章
- IO密集型操作时,为什么线程比进程更好?
- 我的Android进阶之旅------>如何获取系统中定义了那些权限
- $.ajax()方法详解(转)
- 正则表达式备忘(基于JavaScript)
- 保持linux下保持ssh不断线
- Kattis - fire2 【BFS】
- iOS 发大招 otherButtonTitles:(nullable NSString *)otherButtonTitles, ... 写法 &;&; 编写通用类的时候关于可变参数的处理
- 为jquery添加扩展标准思路
- 0417 封装 property、classmethod、staricmethod
- linux挂载/卸载优盘