首页 > 代码库 > 在数组中找出x+y+z=0的组合
在数组中找出x+y+z=0的组合
就是找x+y=-z的组合
转化为找出值为-z满足x+y=-z的组合
解法一:
为了查找,首先想到排序,为了后面的二分,nlogn,
然后x+y的组合得n^2的复杂度,加上查找是否为-z,复杂度为nlogn + n^2 * logn
解法二:
还是先从小到大排序 nlogn
假设数组排序后为 a b c d e f
我们还是要找x+y=-z
会发现-z存在的可能只能是a+f和b+e,不会存在a+e和b+f这种情况(这里很重要,保证了算法的正确性),所以两个指针一头一尾往中间扫,肯定能找出来
fist + last < sum 则将fist++,如果fist + last > sum,则last--。这样的话只要对每个进行这种查找就好了
所以复杂度为nlogn+n*n
在数组中找出x+y+z=0的组合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。