给定一个数字数组,找出其中3个数字之和是否等于0
给定一个数字数组,找出其中3个数字之和是否等于0。
在N ^ 2中执行此操作,该怎么做?
回答:
没有哈希表的O(n ^ 2)解决方案(因为使用哈希表作弊:P)。这是伪代码:
Sort the array // O(nlogn)for each i from 1 to len(array) - 1
iter = i + 1
rev_iter = len(array) - 1
while iter < rev_iter
tmp = array[iter] + array[rev_iter] + array[i]
if tmp > 0
rev_iter--
else if tmp < 0
iter++
else
return true
return false
基本上使用排序数组,对于数组中的每个数字(目标),您将使用两个指针,一个指针从数组的前部开始,一个指针从数组的后部开始,检查指针所指向的元素的总和是否>
,<或==到目标,并相应地使指针前进,或者如果找到目标,则返回true。
以上是 给定一个数字数组,找出其中3个数字之和是否等于0 的全部内容, 来源链接: utcz.com/qa/402783.html