有长短不同的木棒若干根。
例如长度分别为【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; ?>
新坛装陈酒, 经典的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;
}
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;
};
刚好最近在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
#!/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)
如果有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)
结合@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; }
根据楼主的例子，接下：
<?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) 不需要额外空间