【日本Google算法面试题分享】

Question

有长短不同的木棒若干根。
例如长度分别为【8, 4, 10, 3, 2】这五根木棒，
从中任取3根木棒组合，长度正好为15的有[8,3,4]、[10,3,2]两种组合。
其中组合的顺序[8,4,3][8,3,4][4,3,8]...视为相同组合，同时必须保证正好3根木棒，一根或者两根组合不可。

根据上面描述，有count(1<=count<=5000)个不重复的数字，求从中取出3个数字，相加之和正好为sumLength（最大32bit）的组合有多少？

要求 考虑性能，尽量避免多余Loop循环，实现语言不限。

php <?php
// 测试值
$sumLength = 15;          // 组合后长度
$count = 5;               // 不重复数字数量
$bars = [8, 4, 10, 3, 2]; // 不重复数字组合

$answer = 0;
/*
* 处理代码
*/
echo $answer;
?>

Answer 1

#!/usr/bin/python

def answer(numbers, sumLength):
    count = len(numbers)
    if count < 3: raise Exception("bad input")
    numbers = sorted(numbers)
    existence = set(numbers)
    result = []
    for i in range(count):
        for j in range(i + 1, count):
            a, b = numbers[i], numbers[j]
            c = sumLength - a - b
            if c in existence and c > b:
                result.append([a, b, c])
    return result

print answer([8,4,10,3,2], 15)

Answer 2

如果有a<b<c，且a+b+c = N

那么一定有，a<N/3,b<N/2,

for(a = s[BEGIN];a<N/3;a++)
    for(b = a+1;b<N/2;b++) 
      for(c = N/3;c<S[END];c++)
      if(a+b+c == N) print(a,b,c)

Answer 3

新坛装陈酒, 经典的3sum问题.

一般的做法就是@felix021的, sort后, 两次循环, 去hash中查. 时间O(n^2), 空间O(n).

至于给 循环变量 限定上界的做法, 没有改变时间复杂度.

此题还有一个比较有趣的变化, 不预先建好hash, 而是在 每次外循环结束时 逐渐加入hash.

public List<int[]> threeSum(int[] nums, int target){
    if(nums == null || nums.length < 3)
        return Collections.emptyList();

    Arrays.sort(nums);
    Set<Integer> set = new HashSet<>();
    set.add(nums[0]);
    List<int[]> list = new ArrayList<>();
    int len = nums.length;
    for(int i = 1; i < len - 1; i++){
        for(int j = i + 1; j < len; j++){
            int n = target - nums[i] - nums[j];
            if(set.contains(n))
                list.add(new int[]{n, nums[i], nums[j]});
        }
        set.add(nums[i]);
    }

    return list;
}

Answer 4

3sum问题，https://leetcode.com/problems/3sum/
这里简化了，规定数组中没有重复的数字
js代码如下：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

var threeSum = function(nums) {
    if (nums.length < 3) {
        return [];
    }
    var map = {};
    var res = [];
    //对nums进行排序
    nums.sort(function(a, b) {
        return a - b;
    });
    //console.log(nums);
    var i = 0,
        l = nums.length;

    for (; i < l; i ++) {
        //找到差值
        var k = nums[i];

        var s = i + 1,
            e = l - 1;

        while (s < e) {
            var v = 0 - (nums[s] + nums[e]);
            //console.log(s, e, nums[s] + nums[e], k);
            if (v > k) {
                s ++;
            } else if (v < k) {
                e --;
            } else {
                //find it!
                //可能会有重复的
                var temp = [k, nums[s], nums[e]];
                var key = temp.join('#');

                if (!map[key]) {
                    res.push(temp);
                    map[key] = true;
                }
                //这个时候应该继续找下去
                s ++;
                e --;
            }
        }
    }
    return res;
};

Answer 5

结合@felix021 @tiyee 给出的答案，目前给出一个认为较好的答案。
欢迎大家指正！

phpfunction getResult($bars, $sumLength) {
    // 初始结果
    $answer = 0;
    // 数组元素个数
    $count = count($bars);
    // PHP内置函数排序从小到大
    sort($bars);
    // sum[a, b, c] = $sumLength　必須条件 "a < $sumLength/3" && "b < $sumLength/2"
    $a_max = $sumLength/3;
    $b_max = $sumLength/2;

    for($i = 0; $i < $count - 1 && $bars[$i] < $a_max; $i++) {
        $a = $bars[$i];
        for ($j = $i + 1; $j < $count && $bars[$j] < $b_max; $j++) {
            $b = $bars[$j];
            $c = $sumLength - $a - $b;
            if($c > $b && in_array($c, $bars)) {
                $answer++;
            }
        }
    }
    return $answer;
}

Answer 6

根据楼主的例子，接下：

<?php
// 测试值
$sumLength = 11;          // 组合后长度
$bars = [8, 4, 10, 3, 2]; // 不重复数字组合
$bars = [1,2,3,4,5,6,7]; // 不重复数字组合

$answer = 0;
sort($bars);
$i1 = 0; // 开始位置第一个
$i2 = 1; // 紧接第二个
$i3 = count($bars) - 1; // 最后一个
$l  = 1;
while( $i1+1 < $i3 ){ // 如果第一个和最后一个不接近
    $sum = $bars[$i1] + $bars[$i2] + $bars[$i3];
    if( $sum >= $sumLength || $i2+1>=$i3 ){
        if( $sum == $sumLength ){
            echo "ok:{$bars[$i1]},{$bars[$i2]},{$bars[$i3]}\n";
            $answer++;
        }
        if( $l == 0){ $i1++; $l=1; }
        else{ $i3--; $l=0; }
        $i2 = $i1;
    }
    $i2 ++;
}
echo $answer ."\n";
?>

答案为：

2,3,10
3,4,8
int(2)

时间复杂度 O(n^2)
空间复杂度 O(1) 不需要额外空间

Answer 7

刚好最近在leetcode做过这个题，我感觉我这个解法只需要O(n^2)的时间复杂度和O(1)的空间复杂度，不知道有没有理解错，leetcode上已经AC了。

class Solution:
    # @param {integer[]} nums
    # @return {integer[][]}
    def threeSum(self, nums, target=0):
        nums = sorted(nums)
        ret = set() # 如果没有相同的需要去重，这里直接用list即可
        for i, n in enumerate(nums):
            pairs = self.two_sum(nums, target-n, i+1) # 排序过的list做two sum只需要O(n)
            if pairs:
                for p in pairs:
                    ret.add((n, p[0], p[1]))
        return list(ret)

    def two_sum(self, nums, target, begin):
        end = len(nums) - 1
        ret = []
        while begin < end:
            _sum = nums[begin] + nums[end]
            if _sum == target:
                ret.append((nums[begin], nums[end]))
                begin += 1
                end -= 1
            elif _sum < target:
                begin += 1
            else:
                end -= 1
        return ret