求正序增长的正整数数组中,其和为 N 的两个数
//=> [5, 10]
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15);
//=> null
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 150);
返回的数组不唯一
const twoSum = (arr, sum) => {
if (arr.length < 2 || arr[arr.length - 1] + arr[arr.length - 2] < sum) {
return null;
}
const sumList = {},
res = [];
for (let i = 0; i < arr.length; i++) {
let val = arr[i];
if (sumList[val]) {
res.push([Math.min(val, sumList[val]), Math.max(val, sumList[val])]);
} else {
sumList[sum - val] = val;
}
}
return res.length === 0 ? null : res;
};
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15); // [[7, 8], [6, 9], [5, 10]]
一,常规两数之和
var twoSum = function (nums, target) {
const hash = new Map();
for (let i = 0; i < nums.length; i++) {
if (hash.has(target - nums[i])) return [nums[i], nums[target - i]];
hash.set(nums[i], i);
}
return null;
};
二,双指针 利用题目的提示 “正序增长的正整数数组” 而且例 1 的提示很明显了,左右两个指针 当前和大于目标值,右指针左移 当前和小于目标值,左指针右移 左指针等于右指针,循环中断,返回 null
const twoSum = (number, target) => {
let left = 0,
right = number.length - 1;
while (left < right) {
const sum = number[left] + number[right];
if (sum === target) return [number[left], number[right]];
// 等于目标值,返回对应值
else if (sum < target) left++;
// 小于目标值,左指针向右移动
else right--; // 大于目标值,右指针向左移动
}
return null;
};
一、获取其中某一种组合
function twoSum(arr, target) {
let first;
let second;
arr.forEach((element) => {
if (arr.includes(target - element)) {
first = element;
}
});
second = arr.find((ele) => ele === target - first);
if (!first || !second) return null;
return [first, second];
}
二、获取所有组合
function twoSum(arr, target) {
let firstArr = [];
let secondArr = [];
let result = [];
arr.forEach((ele) => {
if (arr.includes(target - ele)) {
firstArr.push(ele);
}
});
firstArr.forEach((ele) => {
secondArr.push(target - ele);
});
firstArr.forEach((firstEle, i) => {
secondArr.forEach((secondEle, j) => {
if (i === j) {
result.push([firstEle, secondEle]);
}
});
});
return result.length > 0 ? result : null;
}
双指针法获取所有组合
const twoSum = (arr, sum) => {
if (arr.length <= 1) return [];
let len = arr.length;
let left = 0;
let right = len - 1;
let result = [];
while (left < right) {
let _sum = arr[left] + arr[right];
if (_sum === sum) {
result.push([arr[left], arr[right]]);
left++;
right--;
} else if (_sum > sum) {
right--;
} else {
left++;
}
}
return result;
};