这是否在 O(N log(N)) 时间内解决了 3SUM?
Does this solve 3SUM in O(N log(N)) time?
此算法是否可以作为 O(N log(N))
中 3SUM 的解决方案,维基百科将问题定义为
In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero.
//Given an array of integers called list
//return true if 3 integers in list sum to 0, false otherwise
//quicksort the provided list
quickSort(list)
//add all elements of the list to a hashmap where the key is a number and the value is the number of times it occurs
hs = new hashMap<Integer, Integer>()
for(Integer i:list)
if(hs.get(i)==null)
hs.add(i, 1)
else
hs.add(i, hs.get(i)+1)
//create a pair of pointers pointing to the left of right of the center of array
startIndex=0
while (list[startIndex]<0 and startIndex<list.length-1)
startIndex++
left=startIndex
right=startIndex+1
//run this loop while pointers are in boundaries of array
while(! (left<0 or right>=list.length)
{
//see if a 3rd number that can be added to the numbers at left
//and right to make 0 can be found
sum=list[left] + list[right]
negsum= -(sum)
//if it's found enter these if statements
if(hs.get(negsum)!=null)
{
//check for the possibility that the 3rd number is one of the 1st 2, if not return true
if(negsum==list[left] or negsum== list[right])
{
//if the 3rd number is one of the 1st 2 make sure that a duplicate of it exists, or if all 3 are 0, that 3 zeros exist
//if we have enough duplicates, return true
if(list[left]==list[right] )
if(list.hasMoreThanTwo(negsum))
return true
else if(list.hasMoreThanOne(negsum))
return true
}
else
return true
}
//if a trio cannot be formed with the numbers at left and right, adjust the pointers so that we will get closer to 0 and try again.
if (sum<0)
right++
else
left--
}
//if pointers go out of bounds 3 numbers that sum to 0 don't exist
return false
如果我理解算法——你没有在高层次上解释——它就不会起作用。看起来该方法是从最小量级的正数(右)和负数(左)开始工作。对于每一对,您寻找第三个数字使 0。然后将一个边界移动到下一个更大的数字,使 2 个数字的总和接近 0。
问题是您根本不能保证包含一个相对接近 0 的数字的三元组。例如,
[-5100, -1700, -1600, -1000, , 2500, 2600, 5000]
会看到您跳过 left 从 -1600 到 -1700,然后再 right 到 2600 找到解决方案。
您的代码无法处理这种情况:
[-10, -7, 0, 0, 4, 6].
在这种情况下,右指针将越界,因为左指针将位于 -10,这太大了。
因此,如果某件事确实是负面的,您的算法将尝试寻找正面的解决方案,但最终会失败。
如前所述,您的代码并未涉及所有可能的组合。在这里,我将回顾一个测试用例,其中您的代码未能考虑所有可能性。
我们有以下数组:
[101, 100, 100, 0, -50, -199, -200]
为了方便使用,已经整理好了。这被转换为:
{101: (1, 0), 100:(2, 1), 0:(1, 2), -50:(1, 3), -199:(1, 4), -200:(1, 5)}
[101, 100, 0, -50, -199, -200]
我们从值的中心开始,在本例中为 0 和 -50。
在第一次迭代中,我们可以看到没有任何匹配项,因此我们向左移动,因为这会导致更接近的近似值。 (0 + -199 对比 100 + -50)
下一次迭代,我们向右移动。 (100 + -199 对比 101 + -50)
之后的迭代,我们再次向右移动,因为它更接近 0。(101 + -199 vs 100 + -200)
您可能已经注意到,我们刚刚跳过了 100 和 -200 的配对,这是本例中三元组 (100, 100, -200) 中的相关配对。
此算法是否可以作为 O(N log(N))
中 3SUM 的解决方案,维基百科将问题定义为
In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero.
//Given an array of integers called list
//return true if 3 integers in list sum to 0, false otherwise
//quicksort the provided list
quickSort(list)
//add all elements of the list to a hashmap where the key is a number and the value is the number of times it occurs
hs = new hashMap<Integer, Integer>()
for(Integer i:list)
if(hs.get(i)==null)
hs.add(i, 1)
else
hs.add(i, hs.get(i)+1)
//create a pair of pointers pointing to the left of right of the center of array
startIndex=0
while (list[startIndex]<0 and startIndex<list.length-1)
startIndex++
left=startIndex
right=startIndex+1
//run this loop while pointers are in boundaries of array
while(! (left<0 or right>=list.length)
{
//see if a 3rd number that can be added to the numbers at left
//and right to make 0 can be found
sum=list[left] + list[right]
negsum= -(sum)
//if it's found enter these if statements
if(hs.get(negsum)!=null)
{
//check for the possibility that the 3rd number is one of the 1st 2, if not return true
if(negsum==list[left] or negsum== list[right])
{
//if the 3rd number is one of the 1st 2 make sure that a duplicate of it exists, or if all 3 are 0, that 3 zeros exist
//if we have enough duplicates, return true
if(list[left]==list[right] )
if(list.hasMoreThanTwo(negsum))
return true
else if(list.hasMoreThanOne(negsum))
return true
}
else
return true
}
//if a trio cannot be formed with the numbers at left and right, adjust the pointers so that we will get closer to 0 and try again.
if (sum<0)
right++
else
left--
}
//if pointers go out of bounds 3 numbers that sum to 0 don't exist
return false
如果我理解算法——你没有在高层次上解释——它就不会起作用。看起来该方法是从最小量级的正数(右)和负数(左)开始工作。对于每一对,您寻找第三个数字使 0。然后将一个边界移动到下一个更大的数字,使 2 个数字的总和接近 0。
问题是您根本不能保证包含一个相对接近 0 的数字的三元组。例如,
[-5100, -1700, -1600, -1000, , 2500, 2600, 5000]
会看到您跳过 left 从 -1600 到 -1700,然后再 right 到 2600 找到解决方案。
您的代码无法处理这种情况:
[-10, -7, 0, 0, 4, 6].
在这种情况下,右指针将越界,因为左指针将位于 -10,这太大了。
因此,如果某件事确实是负面的,您的算法将尝试寻找正面的解决方案,但最终会失败。
如前所述,您的代码并未涉及所有可能的组合。在这里,我将回顾一个测试用例,其中您的代码未能考虑所有可能性。
我们有以下数组:
[101, 100, 100, 0, -50, -199, -200]
为了方便使用,已经整理好了。这被转换为:
{101: (1, 0), 100:(2, 1), 0:(1, 2), -50:(1, 3), -199:(1, 4), -200:(1, 5)}
[101, 100, 0, -50, -199, -200]
我们从值的中心开始,在本例中为 0 和 -50。
在第一次迭代中,我们可以看到没有任何匹配项,因此我们向左移动,因为这会导致更接近的近似值。 (0 + -199 对比 100 + -50)
下一次迭代,我们向右移动。 (100 + -199 对比 101 + -50)
之后的迭代,我们再次向右移动,因为它更接近 0。(101 + -199 vs 100 + -200)
您可能已经注意到,我们刚刚跳过了 100 和 -200 的配对,这是本例中三元组 (100, 100, -200) 中的相关配对。