3Sum

[barretlee]

本题难度：★★

给定一个整数数组 S，找到所有的三元元组 (a, b, c)，使得 a + b + c = 0，注意，

• (a, b, c) 中 a ≤ b ≤ c
• 不要输出重复的元组

比如：

给定 S = [-1, 0, 1, 2, -1, -4]，输出 [[-1, 0, 1], [-1, -1, 2]]

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/12.md

[daghlny]

先记录每个 element 出现的次数，然后去掉序列中的重复 element。用暴利枚举搜索所有可能的组合，这样可以保证每个元组只会被搜索到一遍。

[barretlee]

@daghlny 这道题不需要太暴力，从题设看，必然有一个负数和一个正数（或者都是 0）。

[daghlny]

en, 谢谢指点，我没考虑到这个特点。

[777720]

先排序，然后先拿出一个数，转化成两数和的问题，暂时只能想到这了 QAQ。。。。。

[barretlee]

这代码写的略恶心...

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]]));

[barretlee]

这道题使用红黑树应该能快不少。

[pixcai]

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]))

试着写了一下，有什么不对的地方请多多指教。

[Min-field]

感觉写的好长。。。
时间复杂度 O(n*n)

/**
 * @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]]));

 

[daghlny]

为什么楼上的都是 js 代码

int sum3(int *nums, int n)
{
    if (n < 3) return -1;
    int result_num = 0;
    sort(nums, nums+n);
    for (int i = 0; i < n-2; ++i)
    {
        if ( i > 0 && nums[i] == nums[i-1] ) continue;

        int low = i+1, high = n-1;
        while( low < high )
        {
            int target = -(nums[i]);
            if ( nums[low] + nums[high] == target ){
                printf("%d %d %d\n", nums[i], nums[low], nums[high]);
                ++result_num;
                do{
                    --high;
                }while(high > 0 && nums[high] == nums[high+1]);
                do{
                    ++low;
                }while(low < n && nums[low] == nums[low+1]);
            }
            else if ( nums[low] + nums[high] < target )
                ++low;
            else
                --high;
        }
    }
    return result_num;
}

[dahuanggithub]

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));

[pixcai]

@barretlee 和 @Min-field 的代码都是错的，当输入列表[0, 1, 1, 2, -1, -3]时，结果就不对了。

另外，我用Benchmark把 @dahuanggithub 的代码和我的代码分别用长度为10、50、100、500、1000的随机整数数组进行了测试，发现 @dahuanggithub 的代码性能是最好的，不过之后我把我的代码又修改了一番，终于追上 @dahuanggithub 的性能了，@_@。

另外，我在实现上没有区分正负数，而 @dahuanggithub 区分了正负数。

[YabZhang]

def two_sum(seq, start, end, sum_):
    result = []
    head, tail = start, end
    while head < tail:
        if seq[head] + seq[tail] < sum_:
            head += 1
        elif seq[head] + seq[tail] > sum_:
            tail -= 1
        else:
            result.append([seq[head], seq[tail]])
            tail -= 1
    return result

def three_sum(seq, sum_):
    result = []
    n_seq = sorted(seq)
    for i in range(len(seq)):
        if n_seq[i] > 0:
            # filter
            return list(eval(item) for item in set([str(ss) for ss in result]))
        tmpr = two_sum(seq, i + 1, len(seq) - 1, sum_ - n_seq[i])
        if tmpr:
            result += [[n_seq[i]] + sub for sub in tmpr]

[youngwind]

@pixcai 你运行的 Benchmark 测试用例有源码吗？我想实际看看怎么给这几个不同的算法进行性能对比。

[pixcai]

@youngwind 呃，源码早删了，你看看Benchmark的文档怎么测吧，我是按照它的文档写的测试。