3Sum about daily-algorithms HOT 14 OPEN

function resolve(S) {
  var triples = [], sMap = {}, negArr = [], posArr = [], tmp;
  for (var i = 0, len = S.length; i < len; i++) {
    if (!sMap[S[i]]) {
      if (S[i] < 0) {
        negArr.push(S[i]);
      } else if (S[i] > 0) {
        posArr.push(S[i]);
      }
    }
    sMap[S[i]] = (sMap[S[i]] || 0) + 1;
  }

  // [0, 0, 0]
  if (sMap[0] >= 3) triples.push([0, 0, 0]);

  // [-a, 0, a]
  for (i = 0, len = negArr.length; i < len; i++) {
    tmp = negArr[i];
    sMap[-1 * tmp] && triples.push([tmp, 0, -1 * tmp]);
  }

  // [-2a, a, a]
  for (i = 0, len = negArr.length; i < len; i++) {
    tmp = negArr[i];
    tmp % 2 === 0 && sMap[tmp] >= 2 && sMap[-2 * tmp] && triples.push([tmp, tmp, -2 * tmp]);
  }

  // [-a, -a, 2a]
  for (i = 0, len = posArr.length; i < len; i++) {
    tmp = posArr[i];
    tmp % 2 === 0 && sMap[-1 * tmp / 2] >= 2 && triples.push([-1 * tmp / 2, -1 * tmp / 2, tmp]);
  }

  // [-a, -b, a + b]
  for (var i = 0, len = negArr.length; i < len - 1; i++) {
    for (var j = i + 1; j < len; j++) {
      tmp = sMap[-1 * (negArr[i] + negArr[j])];
      if (tmp) {
        if (negArr[i] > negArr[j]) {
          triples.push([negArr[j], negArr[i], tmp]);
        } else {
          triples.push([negArr[i], negArr[j], tmp]);
        }
      }
    }
  }

  // [-a + -b, a, b]
  for (var i = 0, len = posArr.length; i < len - 1; i++) {
    for (var j = i + 1; j < len; j++) {
      tmp = sMap[-1 * (posArr[i] + posArr[j])];
      if (tmp) {
        if (negArr[i] > negArr[j]) {
          triples.push([negArr[j], negArr[i], tmp]);
        } else {
          triples.push([negArr[i], negArr[j], tmp]);
        }
      }
    }
  }
  return triples;
}

var triples = resolve([-1, 0, 1, 2, -1, -4]);
console.assert(JSON.stringify(triples) === JSON.stringify([[-1, 0, 1], [-1, -1, 2]]));

function resolve(list) {
    var sortedList = list.sort(function(a, b) {
        return (a < b ? -1 : a > b ? 1 : 0)
    })
    var result = [], LIST_LENGTH = sortedList.length, LAST_SECOND = LIST_LENGTH - 2

    if (LIST_LENGTH >= 3) {
        var first = 0, second = 1, inResult = {}, computing = true

        while (computing) {
            var a = sortedList[first], b = sortedList[second], v = [a, b].join()

            for (var third = second + 1; third < LIST_LENGTH; third++) {
                var c = sortedList[third]

                if ((a + b > 0) || (a + b < 0 && c > -(a + b))) break

                if ((a + b + c === 0) && (inResult[c] !== v)) {
                    inResult[c] = v
                    result.push([a, b, c])
                }
            }
            if ((first < LIST_LENGTH - 3) && (second <= LAST_SECOND)) {
                second = (second === LAST_SECOND) ? (++first, first + 1) : ++second
            } else {
                computing = false
            }
        }
    }

    return result
}

console.log(resolve([-1, 0, 1, 2, -1, 4]))

/**
 * @param  {Array} nums
 * @return {Array[Array]} res
 */
function threeSum(nums){
    if(nums.length < 3) 
        return []; 
    let minPositiveIdx = -1, 
        maxNegativeIdx = -1, 
        zeroStartIdx = -1,
        zeroEndIdx = -1,
        res = []; 

    // 预处理数组
    // 找到最大的负数位置，最小的正数位置
    nums.sort((a, b) => a - b); 
    for(let i = 0; i < nums.length - 1; i++){
        if(nums[i] === 0){
            zeroStartIdx = i; 
            while(i < nums.length && nums[i] === 0)
                i++; 
            i--; 
            zeroEndIdx = i; 
            if(i + 1 < nums.length && nums[i + 1] > 0){
                minPositiveIdx = i + 1; 
                break; 
            }
        } else if (nums[i] < 0  && nums[i+1] >= 0){
            maxNegativeIdx = i; 
            if(nums[i+1] > 0){
                minPositiveIdx = i + 1; 
                break; 
            }
        } 
    }

    if(zeroEndIdx - zeroStartIdx >= 2)
        res.push([0, 0, 0]); 
    if(minPositiveIdx === -1 || maxNegativeIdx === -1)
        return res; 

    // 三元组中有0的情况
    if(zeroStartIdx != -1)
        twoSum(0, nums.length - 1, maxNegativeIdx, minPositiveIdx, 0, -1); 

    // 两负一正的情况
    for(let i = 0; i <= maxNegativeIdx; i++){
        twoSum(0, nums.length - 1, maxNegativeIdx, minPositiveIdx, -1 * nums[i], i); 
        while(i + 1 <= maxNegativeIdx && nums[i] === nums[i+1])
            i++; 
    }

    // 两正一负的情况
    for(let i = minPositiveIdx; i < nums.length; i++){
        twoSum(0, nums.length - 1, maxNegativeIdx, minPositiveIdx, -1 * nums[i], i); 
        while(i + 1 <= nums.length - 1 && nums[i] === nums[i+1])
            i++; 
    }

    /**
     * 计算一个排序数组内加起来为 某个定值 的两个数
     * 具体方法为两个迭代器分别从前和从后 两个方向向中间行进，根据两者之和 target 的比较 
     * 确定接下来迭代器的行为，并解决重复问题
     * 
     * @param  {number} frontIdx    向后迭代器初始位置
     * @param  {number} backIdx     向前迭代器初始位置
     * @param  {number} frontLimit  向后迭代器边界
     * @param  {number} backLimit   向前迭代器边界
     * @param  {number} target      目标值
     * @param  {number}  confict    目标值的相应位置
     * @return {number}
     */
    function twoSum(frontIdx, backIdx, frontLimit, backLimit, target, confict){
        let front = frontIdx, 
            back = backIdx; 

        while(front <= frontLimit && back >= backLimit){
            if(front === confict){
                front ++; 
                continue; 
            }

            if(back === confict){
                back --; 
                continue;
            }

            if(nums[front] + nums[back] > target){
                while(back - 1 >= backLimit && nums[back] === nums[back-1])
                    back --; 
                back--;
            } else if(nums[front] + nums[back] < target){
                while(front + 1 <= frontLimit && nums[front] === nums[front + 1])
                    front ++; 
                front++; 
            } else {
                res.push([nums[front], -1 * target, nums[back]]); 
                while(back - 1 >= backLimit && nums[back] === nums[back-1])
                    back --; 
                back--; 
                while(front + 1 <= frontLimit && nums[front] === nums[front + 1])
                    front ++; 
            }
        }
    }
    return res; 
}

let nums = [-1, 0, 1, 2, -1, -4]; 
console.assert(JSON.stringify(threeSum(nums)) === JSON.stringify([[-1, 0, 1], [-1, -1, 2]]));

 

function myFunction(arr){
  var positive = [];
  var negative = [];
  var zero = [];
  var res = [];
  for(var i=0;i<arr.length;i++){
    if(arr[i] < 0&&arr[i]!=arr[i+1]){
      negative.push(arr[i]);
    }else if(arr[i] === 0){
      zero.push(arr[i]);
    }else if(arr[i] > 0 && arr[i] != arr[i+1]){
      positive.push(arr[i]);
    }
  }
  function f(x){
    for(var j=0;j<negative.length;j++){
      var _arr = arr.slice(arr.indexOf(negative[j])+1);
      _arr = _arr.reverse().slice(_arr.indexOf(x)+1);
      var v = -x-negative[j];
      if(_arr.indexOf(v)>=0){
        res.push([negative[j],-x-negative[j],x]);
      }
    }
  }
  positive.map(f);
  if(zero.length>2){
    res.push([0,0,0]);
  }
  return res;
}
 
var d=[-8,4,-5,-5,-1,0,0,0,0,1,7,-6,10,10];

d.sort(function (x, y) {
  if (x < y) {
      return -1;
  }
  if (x > y) {
      return 1;
  }
  return 0;
});
console.log(myFunction(d));