这是否解决O（N log（N））时间中的3SUM？

是否该算法工作在O(N log(N))为3SUM一个解决方案，该问题是由维基百科这是否解决O（N log（N））时间中的3SUM？

在计算复杂性理论定义的，3SUM问题询问一组给定ň实数包含三个元素总和为零。

//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

来源

2017-09-01 Zainan

您的算法不会覆盖所有选项... – alfasin

嗯。您的代码不处理这种情况下：

[-10，-7，0，0，4，6]。

在这种情况下，正确的指针会去出界，因为左指针会在-10，这是太大了。

所以，如果某件事真的是消极的，你的算法会尝试寻找一个积极的解决方案，并最终失败。

来源

2017-09-02 02:36:44

如果我理解算法 - 你没有在高水平解释 - 它不会工作。看来，这种方法是从最小幅度的正数（右）和负数（左）开始工作。对于每一对，你看第三个号码进行清零。然后你一个框移动到下一个较大的数目，保持2个和接近0

的问题是，你并不保证三重包含一个数字比较接近为0。举例来说，像

的[-5100，-1700，-1600，-1000，2500，2600，5000]

会看到你跳过左过去-1600到-1700之前你得到正确到2600找到解决办法。

来源

2017-09-01 22:59:56 Prune

我没有看到包含-1100的三元组，总计为0. – Zainan

精神错过1,000 ...谢谢。 – Prune

如前所述，您的代码不涉及所有可能的组合。在这里，我将介绍一个测试用例，其中代码未能考虑所有可能性。

我们有以下阵列：

[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 VS 100 + -50）

的下一次迭代，我们向右移动。（100 + -199 VS 101 + -50）

迭代后，我们向右移动再次，因为这是近于0（101 + -199 VS 100 + -200）

正如你可能已经注意到了，我们刚刚跳过了100和-200的配对，在这种情况下，这是三元组（100，100，-200）中的相关配对。

来源

2017-09-02 04:10:22 AlterionX

这是否解决O（N log（N））时间中的3SUM？

回答

相关问题