Algorithms Analysis

[barretlee]

从一堆顺序排列的整数中任选三个，其和为 0 则为一组，类似这样的组有多少？

分析方法：任选两个组合为 0，得出一个暴力算法：twoSum.js，类比可以得到 threeSum.js

两个算法的时间复杂度都是很高的，结合 #1 提到的二分法降低复杂度，得到：twoSumFast.js 和 threeSumFast.js。

代码地址：/chapters/chapter-1-fundamentals/1.4-analysis-of-algorithms/threeSumFast.js

function threeSumFast(input) {
  var counter = 0;
  for(var i = 0, len = input.length; i < len - 2; i++) {
    for(var j = i; j < len - 1; j++) {
      var searchKey = -1 * (input[i] + input[j]);
      if(rank(input, searchKey) > -1) {
        counter++;
      }
    }
  }
  return counter;

  function rank(a, k){
    var start = 0;
    var end = a.length - 1;
    while(start <= end) {
      var mid = Math.floor((end - start) / 2) + start;
      if(k < a[mid]) {
        end = mid - 1;
      } else if(k > a[mid]) {
        start = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  }
}