create question - #136
Conversation
function anwser (arr, target) {
let map = {}
for (let i = 0; i < arr.length; i++) {
map[arr[i]] = i
}
for (let i = 0; i < arr.length; i++) {
var d = target - arr[i]
if (map[d]) {
return [i, map[d]]
}
}
return new Error('404 not found')
} |
var twoSum = function(nums, target) {
const res = []
loop:
for (let i =0; i<nums.length-1; i++){
for (let j = i+1;j<nums.length;j++){
if (nums[i]+nums[j]===target){
res.push(i,j)
break loop
}
}
}
return res
}; |
function sum(arr, target) {
const res = []
for (let i = 0; i < arr.length; i++){
const a = target - arr[i]
const index = arr.indexOf(a,i)
if (index>=0) {
res.push(i, index)
}
}
return res
}循环一次 |
|
function twoSums(nums, target) { |
没考虑重复啊 |
|
var arr = [2,3,4,1,6,9,0,7],target = 9; |
|
arr.reduce((res, cval, index) => { |
|
这样太简单了,直接index解决: arr.reduce((res, cur, i) => {
const index = arr.findIndex(x => x === target - cur);
return res || (!!~ index && [i, index])
}, void 0);题目可以增加一点难度,找出arr中所有的和为target的元素子集: function findTarget(arr, target) {
const res = { idx: [], ele: [] };
!function dp(target, index, memoryIndex = [], memoryEle = []) {
const remain = target - arr[index];
if (remain === 0) {
res.idx.push(memoryIndex);
res.ele.push(memoryEle);
}
if (index + 1 >= arr.length) {
return;
}
for (let i = index + 1; i < arr.length; i++ ) {
dp(remain, i, [...memoryIndex, i], [...memoryEle, arr[i]])
}
}(target, 0, [0], [arr[0]]);
return res;
} |
当arr = [4, 7, 11, 15], target = 8的时候会有问题,结果是[0, 0], 显然是有问题的 |
下面单元测试可以通过 |
|
可以使用二分查找来提高效率 var twoSum = (nums, target) => {
if (nums.length < 2) {
throw new Error("至少提供两个数字")
}
if (nums.length === 2) {
if (nums[0] + nums[1] === target) {
return nums;
}
throw new Error("没找到")
}
nums = nums.sort((a, b) => a - b);
let l = Math.floor(nums.length / 2);
let s = l - 1;
while(s >= 0 && l <= nums.length - 1) {
let a = nums[s]
let b = nums[l]
if (a + b < target) {
l = Math.floor((l + nums.length - 1) / 2);
continue;
} else if (a + b > target) {
s = Math.floor((s + 0) / 2);
} else {
return [a, b]
}
}
throw new Error("没找到")
} |
二分总体优化不大。。都上排序了 复杂度已经上去了。。 |
|
利用空间换时间: const twoNum = (nums, target) => {
const maps = {};
for(let i = 0, len = nums.length; i < len; i++) {
let diff = target - nums[i];
if (maps[diff] > -1) {
return [maps[diff], i];
}
maps[nums[i]] = i;
}
return [];
} |
|
|
function getIdx(ary, target) { |
|
加个判断 |
|
const sum = (nums, target) => { console.log(sum([2, 11, 15, 7, 9, 8], 23)) |
|
|
|
const findSum = (nums, target) => {
const obj = {}
for(let i = 0; i < nums.length; i++){
const val = nums[i]
if(typeof obj[val] !== 'undefined'){
return [obj[val], i]
} else {
obj[target - val] = i
}
}
}
const nums = [2, 7, 11, 15], target = 9
console.log(findSum(nums, target)) |
|
|
双指针,两个额外的变量,时间复杂度O(n) function findSumIndex (nums, target) {
let left = 0
let right = nums.length - 1
while (left < right) {
const sum = nums[left] + nums[right]
if (sum > target) {
right--
} else if (sum < target) {
left++
} else {
return [left, right]
}
}
} |
nums = [2, 11, 7, 15], target = 9
try {
nums.forEach((k, v) => {
nums.splice(v, 1, undefined)
nums.forEach((kk, vv) => {
if (k + kk === target) {
throw Error([v ,vv])
}
})
})
} catch(data){
console.log(data)
} |
|
用差值和 function fn(arr, target) {
for (let i = 0; i < arr.length; i++) {
const find = target - arr[i];
const idx = arr.lastIndexOf(find);
if (idx !== -1 && idx !== i) {
return [i, idx];
}
}
return [];
}
console.log(fn([2, 7, 11, 15], 9)); // [0,1]
console.log(fn([2, 4, 15], 8)); // []
console.log(fn([2, 4, 4, 15], 8)); // [1,2]
console.log(fn([2, 4, 8, 0, 3, 4, 15], 7)); //[1,4] |
function searchTargetIndex(arr, target) {
const map = new Map()
for (let index = 0; index < arr.length; index++) {
const curVal = arr[index]
const restval = target - curVal
if (map.has(restval)) {
return [map.get(restval), index]
} else {
map.set(curVal, index)
}
}
return []
}
console.assert(JSON.stringify(searchTargetIndex([2, 7, 11, 15], 9)) === JSON.stringify([0, 1]))
console.assert(JSON.stringify(searchTargetIndex([4, 7, 11, 15], 8)) === JSON.stringify([])) |
var arr = [4, 7, 11, 15, 4, 3, 15];
function findAll(arr, sum) {
var map = {};
var valueList = [];
for (let i = 0; i < arr.length; i++) {
var n = arr[i];
if (map[sum - n] !== undefined) {
map[sum - n].forEach((index) => {
valueList.push(index + "-" + i);
});
}
if (map[n]) {
map[n].push(i);
} else {
map[n] = [i];
}
}
return valueList;
}
function findOne(arr, sum) {
var map = {};
var valueList = [];
for (let i = 0; i < arr.length; i++) {
var n = arr[i];
if (map[sum - n] !== undefined) {
valueList = `${map[sum - n]}-${i}`;
break;
}
map[n] = i;
}
return valueList;
}
console.log(findAll(arr, 8));
console.log(findOne(arr, 8));
console.log(findAll(arr, 26));
console.log(findOne(arr, 26));
console.log(findAll(arr, 11));
console.log(findOne(arr, 11));
// [ '0-4' ]
// 0-4
// [ '2-3', '2-6' ]
// 2-3
// [ '0-1', '1-4' ]
// 0-1 |
|
|
`let nums = [1, 2, 3, 4, 5, 6, 7, 11, 15]; |
|
function sumofTwo(arr,target){
let res = [];
for(let i=0;i<arr.length;i++){
let flag = arr.indexOf(target -arr[i]); //目标值减去数组中某一个元素,并判断 差 是否在数组中存在
if(flag !== -1 && flag !== i) { //不为-1,并且索引不等于当前元素(排除如2+2 = 4等),不过这里如果是相同的元素,获取的索引会看上去有点别扭
res.push(i,flag);
break; //如题,结果唯一
}
}
return res;
}
console.log(sumofTwo([5,5,10,15],10); //[1,0],这里根据循环判断,i=0时,因为indexOf找到的索引也是0,所以跳过了,i=1时,满足if条件,即结果为[1,0]
console.log(sumofTwo([5,0,10,15],10); //[1,2] |
|
使用Map,记录目前已经遍历过的数字中,达到target所需要的“另一半”数字的值,以及对应的“原配”索引。 由于是先检测是否匹配再添加新键值对,所以不会出现indexOf检测中 arr = [4] 可以达成 target = 8的情况,也不需要额外进行检测。 |
|
const nums = [2,7,11,15, 3, 4, 6, 4, 5];
const target = 9;
const result = [];
const used = [];
for(let i = 0, len = nums.length; i < len; i++) {
if(used.includes(i)) continue;
const idx = nums.findIndex(e => e === target - nums[i]);
if(idx > i && !used.includes(idx)) {
result.push([i,idx]);
used.push(i, idx);
}
}
console.log('result', result); |
|
function fn1(nums, target) { |
let target = 9
let nums = [2, 3, 1, 2, 1, 9, 7, 12, 8, 11, 15, ]
function check(numAry = nums, tag = target) {
const res = []
for (let i = 0; i < numAry.length - 1; i++) {
for (let j = i + 1; j < numAry.length; j++) {
if (numAry[i] !== numAry[j] &&
(numAry[i] + numAry[j]) === tag
) {
res.push(i, j)
return res
}
}
}
return res
}
console.log(check()); |
|
let towNumSum = function (arr, num) {
for (let i = 0; i < arr.length; i++) {
let j = arr.indexOf(num - i, i);
if (j != -1) return [i, j];
}
}; |
|
Map, 空间换时间 |
var sumOfTwoNumber = function (array, target) {
let map = {};
for (let i = 0; i < nums.length; i++) {
let d = target - nums[i];
if (map[d] !== undefined) {
return [map[d], i];
}
map[nums[i]] = i;
}
return [];
}
var nums = [2, 7, 11, 15];
var target = 9
console.log(sumOfTwoNumber(nums, target)); |
|
这是一封自动回复邮件。您好,你的邮件我已收到,会尽快给您回复,祝您生活愉快!
|
|
|
|
这是一封自动回复邮件。您好,你的邮件我已收到,会尽快给您回复,祝您生活愉快!
|
twoNum([1,2,3,4,5,6],7) 输出 【2,3】 |
|
这是一封自动回复邮件。您好,你的邮件我已收到,会尽快给您回复,祝您生活愉快!
|
|
let nums = [2, 7, 11, 15, 17, 25] |
const findSumTarget = (numList, target) => {
const end = numList.length;
const pairList = [];
for (let i=0; i<end; i++) {
for (let cursor = i+1; cursor < end; cursor++) {
if (numList[i] + numList[cursor] === target) {
pairList.push([numList[i], numList[cursor]]);
break;
}
}
}
return pairList;
}
const findSumTargetSimple = (numList, target) => {
const pairList = [];
numList.forEach((v, i) => {
numList.slice(i+1).forEach(item =>
v + item === target && pairList.push([v, item])
)
});
return pairList;
}
const input = [2, 7, 11, 15, 1, 3, 6, 1, 9, 8];
const pairList = findSumTarget(input, 9);
console.log(pairList);
const pairListSimple = findSumTargetSimple(input, 9);
console.log(pairListSimple); |
|
function sumInArr(arr, target) { |
|
No description provided.