Open barretlee opened 7 years ago
先记录每个 element 出现的次数,然后去掉序列中的重复 element。用暴利枚举搜索所有可能的组合,这样可以保证每个元组只会被搜索到一遍。
@Daghlny 这道题不需要太暴力,从题设看,必然有一个负数和一个正数(或者都是 0)。
en, 谢谢指点,我没考虑到这个特点。
先排序,然后先拿出一个数,转化成两数和的问题,暂时只能想到这了 QAQ。。。。。
这代码写的略恶心...
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]))
试着写了一下,有什么不对的地方请多多指教。
感觉写的好长。。。 时间复杂度 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]]));
为什么楼上的都是 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;
}
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));
@barretlee 和 @Min-field 的代码都是错的,当输入列表[0, 1, 1, 2, -1, -3]
时,结果就不对了。
另外,我用Benchmark把 @dahuanggithub 的代码和我的代码分别用长度为10
、50
、100
、500
、1000
的随机整数数组进行了测试,发现 @dahuanggithub 的代码性能是最好的,不过之后我把我的代码又修改了一番,终于追上 @dahuanggithub 的性能了,@_@。
另外,我在实现上没有区分正负数,而 @dahuanggithub 区分了正负数。
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]
@pixcai 你运行的 Benchmark 测试用例有源码吗?我想实际看看怎么给这几个不同的算法进行性能对比。
@youngwind 呃,源码早删了,你看看Benchmark的文档怎么测吧,我是按照它的文档写的测试。
给定一个整数数组 S,找到所有的三元元组
(a, b, c)
,使得a + b + c = 0
,注意,(a, b, c)
中 a ≤ b ≤ c比如:
参考答案:https://github.com/barretlee/daily-algorithms/blob/master/answers/12.md