-
Notifications
You must be signed in to change notification settings - Fork 3.3k
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
create question #136
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) { |
|
加个判断
|
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
quick
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.