New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
求和问题 #20
Comments
2sum左右指针法 function twoSum(nums, target) {
var result = [];
nums.sort((a, b) => a - b);
var i =0, j = nums.length - 1;
while (i < j) {
var sum = nums[i] + nums[j];
if (sum == target) {
result.push([nums[i], nums[j]]);
//处理重复的情况
i++;
j--;
while (i < j && nums[i] == nums[i - 1]) i++;
while (i < j && nums[j + 1] == nums[j]) j--;
} else if (sum < target) {
i++;
} else {
j--;
}
}
// console.log(result)
return result;
}
twoSum( [2, 7, 11, 15], 9) |
3sum上面的变形, twoSum有两个参数,数组与目标值。而3sum则目标值是默认为零, 因此我们从3sum的数组截出一些子数组出来,然后将第一个nums[i]默认为-target, 再找两个数,让它们的和等于target,这样相加就是零。 function threeSum(nums) {
nums.sort((a, b) => a - b);
var res = [];
if (nums.length < 3 || nums[0] > 0 || nums[nums.length - 1] < 0) {
return res;
}
for (var i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
twoSum(nums, i, res); //相当于twoSum(nums, 0, i, res),target总是为零
}
console.log(res);
return res;
}
function twoSum(nums, targetIndex, res) {
var left = targetIndex + 1, target = nums[targetIndex]
right = nums.length - 1;
while (left < right) {
let sum = nums[left] + nums[right] + target
if (sum == 0) {
var temp = [target, nums[left], nums[right]];
res.push(temp);
//去重
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[left - 1]) right--;
left++;
right--;
} else if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
}
}
}
threeSum([-1, 0, 1, 2, -1, -4]); |
4sumfunction twoSum(nums, numsSize, start, target) {
var l = start,
r = numsSize - 1,
res = []
while (l < r) {
var sum = nums[l] + nums[r];
if (sum == target) {
res.push([nums[l], nums[r]]);
//去重
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
} else if (sum > target) {
r--;
} else {
l++;
}
}
return res;
}
function kSum(nums, numsSize, start, k, target) {
if (k == 2) {
return twoSum(nums, numsSize, start, target);
} else {
var kSumRes = [];
for (var i = start; i < numsSize; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
var item = kSum(nums, numsSize, i + 1, k - 1, target - nums[i]); //降维
var itemSize = item.length;
for (var j = 0; j < itemSize; j++) {
item[j].unshift(nums[i]);
kSumRes.push(item[j]);
}
}
console.log(kSumRes)
return kSumRes;
}
}
function threeSum(nums){
if(Object(nums).length < 3){
return []
}
nums.sort((a,b)=>a - b)
return kSum(nums, nums.length, 0, 3, 0 );
}
threeSum([-1, 0, 1, 2, -1, -4]) |
LeetCode 259. 3Sum Smaller求三数之和小于一个目标值 function threeSumSmaller(nums, target){
if(Object(nums).length < 3){
return []
}
nums.sort((a, b)=> a-b);
if(nums[0] >= target){
return []
}
var sum = 0,condidtate = [],result = []
function backtrack(start){
if(condidtate.length == 3){
if(sum < target){
result.push(condidtate.concat())
}
}else{
for(var i = start; i < nums.length; i++){
sum += nums[i]
condidtate.push(nums[i])
backtrack(i+1)
sum -= nums[i]
condidtate.pop()
}
}
}
backtrack(0)
console.log(result)
return result;
}
threeSumSmaller([-2, 0, 1, 3], 2) |
LeetCode 16 3Sum Closest求最接近给定值的三数之和 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example: Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). function threeSumClosest(nums, target) {
nums.sort((a, b) => a - b);
var end = nums.length;
var val = 0, sum = Infinity
function backtrack(start, n) {
if (n == 3) {
if(Math.abs(val - target) < Math.abs(sum - target)){
sum = val
}
} else {
for (var i = start; i < nums.length; i++) {
val += nums[i];
backtrack(i + 1, n+1)
val -= nums[i];
}
}
}
backtrack(0, 0);
console.log(sum);
return sum;
}
threeSumClosest([-1, 2, 1 ,-4], 1); |
3sum
使用回溯法
超时
使用hash法
超时
The text was updated successfully, but these errors were encountered: