时间复杂度：3Sum算法在立方时间内？

Question

如何利用二进制搜索来提高算法的时间复杂度？

我正在审查一些采访的时间复杂度，而且我在使算法更有时间效率方面遇到了麻烦。这是我对3-Sum问题的强力解决方案：有多少三元组总和为0？背景：我没有CS学位。

//BRUTE FORCE SOLUTION: N^3
var threeSum = function(list){
  var count = 0;

  //checking each triple
  for(var i = 0; i < list.length; i++){
    for(var j = i+1; j < list.length; j++){
      for(var k = j+1; k < list.length; k++){

        if(list[i] + list[j] + list[k] === 0){count++;}
      }
    }
  }
  return count;
};

//binary search code
var binarySearch = function(target, array){
  var lo  = 0;
  var hi  = array.length - 1;
  //base case
  while(lo <= hi){
    var mid = Math.floor( lo + (hi - lo) / 2 );
    if(target === array[mid]) return mid;
    if(target < array[mid]){
      hi = mid - 1;
    }
    if(target > array[mid]){
      lo = mid + 1;
    }
  }
  // value not found
  return -1;
}

我正在普林斯顿在线查看算法课程，教授指出，使用二进制搜索算法可以提高算法的效率。

据教授说，我们会：

• 对列表进行排序
• 对于每对数组array [i]＆array [j]二进制搜索 - （array [i] + array [j]）

但是，我无法理解二进制搜索如何解决问题。这是演讲的幻灯片，我仍然试图理解，但也许对其他人有用：

我确信那里有几个有效的解决方案：随意加入您的实施，因为它可以帮助我和其他未来的读者。谢谢

Answer 1

但是，我无法理解二进制搜索如何解决问题。

这就是n ^ 2 log（n）算法的工作原理：

1. 在O（nlogn）时间内对列表进行排序
2. 找到所有数字对(i,j)，它是O（n ^ 2）运行时。
3. 然后，对于每对（i，j），它找到一个数字k，其中k = sum - j - i。这是常数时间O（1）
4. 该算法检查每个k是否存在，因为元组(i,j,k)将总和为sum。要执行此操作，请执行二进制搜索，该搜索需要log（n）时间。

最终运行时间为O（nlogn）+ O（logn * n ^ 2）= O（n ^ 2logn）

另一种（更快）的解决方案是用散列表替换排序部分。然后，查找值k将花费O（1）时间而不是logn

Answer 2

二分搜索方法试图解决的问题是将三次算法（这是你的强力算法）的复杂性降低到~N ^ 2 log N算法中。

正如其他评论者指出的那样，我们知道当下面的陈述：list[i] + list[j] + list[k] == 0是true而不是我们发现的3SUM结果。这就像说-(list[i] + list[j]) == list[k]一样。因此，该算法的目标是检查每个i指数和j指数对，即存在满足前一个等式的相应k指数。二进制搜索可以在~log N时间内找到那些k指数。因此，整体增长顺序为~N ^ 2 log N（外部for循环对应于N ^ 2部分）。

至于在javascript中的实现，我会这样做：

var threesum = function(list) {
  list.sort(function(a,b){return a - b});
  console.log(list);
  var cnt = 0;
  for(var i=0; i<list.length; i++) {
    for(var j=i+1; j<list.length; j++) {
      var k = bsearch(-(list[i]+list[j]), list);
      if (k!= null && k > j) {
        console.log("[i=%d], [j=%d], [k=%d]", i,j,k);
        cnt++;
      }
    }
  }
  return cnt;
};

var bsearch = function(key, a) {
  var lo = 0;
  var hi = a.length-1;
  while (lo <= hi) {
    var mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] < key) {
      lo = mid + 1;
    } else if (a[mid] > key) {
      hi = mid - 1;
    } else {
      return mid;
    }
  }
  return null;
};

threesum([41, 48, 31, 32, 34, 38, 1, -9, 12, 13, 99, 5, -65, 8, 3, -3])

Answer 3

该算法基本上以下列方式工作：

• 排序数组（最坏情况O(n ^ 2)，取决于排序算法）
• 生成所有数字对 - 取O(n ^ 2)
• 对于每对(i , j)，可能存在k，使得0 = i + j + k.kis simply-（i + j）, thus we can easily look it up by binary search inO（log n）. Cases wherei <k <j`不能保持以避免重复。

因此，总时间复杂度是O(n ^ 2 log n)。

Answer 4

const threeSum =(array,target)=>{
  
  let result =[]
  
   array = array.sort((a,b)=> a-b)
  
  for(let i=0; i < array.length-2; i++){
    
    let left = i+1;
    let right = array.length -1;
    
    while(left < right){
      
      let sum = array[i]+ array[left]+ array[right];
      
      if(sum === target){
        result.push([array[i],array[left], array[right]]);
        
        left++;
        right--
      }else if(sum < target){
        
        //sum is lower than target so increment left pointer 
        left++;
      }else if(sum > target){
        //sum is greater than target so increment right pointer 
        right--;
      }
    }
    
    
  }
  //return the list 
  return result;
}

let a = [12, 3, 1, 2, -6, 5, -8, 6];
console.log(threeSum(a, 0));

  Time Complexity: O(n^2) 
  Space Complexity: O(1)