Skip to content

Instantly share code, notes, and snippets.

@599316527
Last active August 15, 2019 09:44
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save 599316527/07ce44a256ac41490576fac1d8bfbb98 to your computer and use it in GitHub Desktop.
N数之和 通解
function threeSum(nums, target) {
return uniq(findN(nums.sort(sortor), target, 3));
};
function fourSum(nums, target) {
return uniq(findN(nums.sort(sortor), target, 4));
};
function findN(nums, target, count, startIndex = 0) {
if (count < 3) return findTwo(nums, target, startIndex);
return nums.reduce(function (ret, val, i) {
if (i < startIndex) return ret;
let result = findN(nums, target - val, count - 1, i + 1);
return ret.concat(result.map(a => [val, ...a]));
}, []);
}
function findTwo(nums, target, startIndex = 0) {
let left = startIndex;
let right = nums.length - 1;
let matched = [];
while (left < right) {
while (nums[left] == nums[left + 2]) left++;
while (right - 2 >= startIndex && nums[right] == nums[right - 2]) right--;
let val = nums[left] + nums[right];
if (val > target) right--;
if (val < target) left++;
if (val == target) {
matched.push([nums[left++], nums[right--]]);
}
}
return matched;
}
function sortor(a, b) {
return a > b ? 1 : -1;
}
function uniq(tuples) {
let map = {};
let ret = [];
for (let i = 0; i < tuples.length; i++) {
if (!map[tuples[i]]) {
ret.push(tuples[i]);
map[tuples[i]] = true;
}
}
return ret;
}
function uniq2(tuples) {
let map = {};
let ret = [];
for (let j = 0; j < tuples.length; j++) {
let t = tuples[j];
let i = 0;
let current = map;
while (i < t.length) {
if (!current[t[i]]) {
current[t[i]] = i + 1 === t.length ? true : {};
}
else if (i + 1 === t.length) {
i = 0;
break;
}
current = current[t[i++]];
}
if (i) {
ret.push(t);
}
}
return ret;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment