首页 > 编程语言 > 详细

九章算法面试题67 3 sum

时间:2015-05-13 10:26:01      阅读:197      评论:0      收藏:0      [点我收藏+]

九章算法官网-原文网址

http://www.jiuzhang.com/problem/68/


题目

给一堆数组和一个目标值,在这堆数组里面找出三个数使得他们的和等于目标值。


在线测试本题

http://www.lintcode.com/en/problem/3-sum/


解答

如果原题的数组中第i个元素我们用ai来表示,目标值我们用v来表示。

这道题的方法非常类似2 sum的第二种解法。首先我们还是先把数组排一个顺序, 然后我们现在还是需要三个指针i,j,k, 我们假设i<j<k,因为我们排了序,那么a[i]<a[j]<a[k], 实际上题意可以转换为a[i]+a[j]+a[k]=v. 我们如果枚举i的话,那么题意又可以转换为在大于a[i]的元素当中寻找a[j]+a[k] = v-a[i] ,那么这个问题就是2sum的问题,所以我们可以用2sum 两个指针指向一头一尾的方法解决这道题。

九章算法面试题67 3 sum

原文:http://blog.csdn.net/jiuzhang_ninechapter/article/details/45682243

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!