Skip to content
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

Merged
merged 9 commits into from
Jul 14, 2019
Merged

create question #136

merged 9 commits into from
Jul 14, 2019

Conversation

blockmood
Copy link
Contributor

No description provided.

@5SSS
Copy link

5SSS commented Jun 3, 2019

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')
}

@harmsworth
Copy link

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
};

@lvwxx
Copy link

lvwxx commented Jun 3, 2019

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
}

循环一次

@Mikerui
Copy link

Mikerui commented Jun 3, 2019

function twoSums(nums, target) {
let subtract
for (let j = 0; j < nums.length; j++) {
subtract = target - nums[j]
for (let i = 0; i < nums.length; i++) {
if (nums[i] == subtract && i !== j) {
return [j, i]
} else {
continue
}
}
}
return false
}

@master-kolan
Copy link

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')
}

没考虑重复啊

@gaoyafengyagao
Copy link

var arr = [2,3,4,1,6,9,0,7],target = 9;
function answer(array,target){
for(let i=0;i<array.length;i++){
let a = target - array[i];
let res = array.indexOf(a,i)
if(res>-1){
console.log(a + "+" + array[i]+"="+9)
}
}
}
answer(arr,target)

@cleverboy32
Copy link

arr.reduce((res, cval, index) => {
if ( res.indexOf(cval) !== -1 ) return;
arr.indexOf(cval) !== -1 && res = res.concat([cval, target-cval]);
}, []);

@lhyt
Copy link

lhyt commented Jun 3, 2019

这样太简单了,直接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;
}

@Vera1128
Copy link

Vera1128 commented Jun 4, 2019

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
}

循环一次

当arr = [4, 7, 11, 15], target = 8的时候会有问题,结果是[0, 0], 显然是有问题的

@NewPrototype
Copy link

NewPrototype commented Jun 4, 2019

function sum(arr:number[],target:number):number[]{
  const len:number=arr.length;
  let index:number=0;
  let disabled:number[]=[];
  let result:number[]=[];
  while (index<len) {
      const endIndex=arr.findIndex((v,i)=>{
          return i!=index&&v+arr[index]==target
      })
      if(endIndex>-1&&!disabled.includes(endIndex)){
        disabled.push(index,endIndex)
        result.push(index,endIndex);
      }
    index++
  }
  return result 
}

下面单元测试可以通过

  it('sum([2, 7, 11, 15,8,2,1],9) to toEqual [0,1,4,6]', () => {
    expect(sum([2, 7, 11, 15,8,2,1],9)).toEqual([0,1,4,6]);
  });
  it('sum([2, 7, 11, 15,8,2,1,5,5],10) to toEqual [0,4,7,8]', () => {
    expect(sum([2, 7, 11, 15,8,2,1,5,5],10)).toEqual([0,4,7,8]);
  });

@BaconZhang
Copy link

BaconZhang commented Jun 4, 2019

可以使用二分查找来提高效率

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("没找到")
}

@francecil
Copy link

可以使用二分查找来提高效率

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("没找到")
}

二分总体优化不大。。都上排序了 复杂度已经上去了。。

@yiqingfeng
Copy link

利用空间换时间:

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 [];
}

@Firenzia
Copy link

Firenzia commented Jun 5, 2019

function getIndex(src, target){
	let list = [...src].sort(function(a,b){return a-b})

	for(let item of list){
		if(list.indexOf(target-item)!== -1){
			return [list.indexOf(item), list.indexOf(target-item)]
		}
	}
	return []
}
var arr= [2,7,11,15]

getIndex(arr,9) // [0,1]

@Younglina
Copy link

function getIdx(ary, target) {
let obj = {};
for (let i = 0; i < ary.length; i++) {
if (obj[ary[i]]!= undefined) {
return [obj[ary[i]], i];
}
obj[target - ary[i]] = i;
}
}

@Chelseasc
Copy link


function convert(arr, target) {
      for(let i in arr) {
          const test = target - arr[i];
          if(arr.includes(test, i)) {
              return [arr.indexOf(arr[i]), arr.indexOf(test)];
          }
     }
     return '未找到';
}

@GuoMeng6
Copy link

GuoMeng6 commented Jun 14, 2019

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
}

循环一次

当arr = [4, 7, 11, 15], target = 8的时候会有问题,结果是[0, 0], 显然是有问题的

加个判断

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 && index !==i) { // index 不能等于 i
      res.push(i, index)
    }
  }
  return res
}

Copy link

@andyliangshan andyliangshan left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

quick

@k-0311
Copy link

k-0311 commented Jun 18, 2019

const sum = (nums, target) => {
for (let [index, val] of nums.entries()) {
let tempIndex = nums.indexOf(target - val)
if (tempIndex > -1) {
return [index, tempIndex]
break
}
}
}

console.log(sum([2, 11, 15, 7, 9, 8], 23))

@Zousdie
Copy link

Zousdie commented Jul 7, 2019

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  if (!Array.isArray(nums) || typeof target !== 'number') {
    return undefined;
  }
  
  var len = nums.length;
  var map = new Map();
  
  for(var i = 0; i < len; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    
    map.set(nums[i], i);
  }
};

@Antelopeclouds
Copy link

function getSum(arr, tar) {
  let reslut = null
  for (let i = 0; i < arr.length; i++) {
    let temp = tar - arr[i]
    arr.includes(temp) && (reslut = [arr[i], arr[arr.indexOf(tar - arr[i])]])
  }
  return reslut
}

@328480460
Copy link

const list = [1, 2, 3, 4, 5, 6, 7, 8];
const target = 13;
const res = [];
for (let i = 0, j = i + 1; i <= list.length;) {
  const start = list[i];
  const end = list[j];
  if (start + end === target) {
    res.push([start, end]);
  }
  j++;
  if (j >= list.length) {
    i++;
    j = i + 1;
  }
}
console.log(res)

@orime
Copy link

orime commented Mar 1, 2021

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))

@ZhengXiaowei
Copy link

function twoSum(nums, target) {
   for(let i = 0; i < nums.length; i++) {
     let nums_slice = nums.slice(0);
     let result = target - nums[i];
     nums_slice.splice(i, 1);
     if (!!~nums_slice.indexOf(result)) {
        let result_key = nums_slice.indexOf(result) + 1;
        return [i, result_key];
     }
     continue;
   }
}

@vdorchan
Copy link

双指针,两个额外的变量,时间复杂度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]
    }
  }
}

@xiangergou
Copy link

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)
}

@zhelingwang
Copy link

zhelingwang commented May 10, 2021

用差值和lastIndexOf比较简单

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]

@NikaSSL
Copy link

NikaSSL commented Jun 23, 2021

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([]))

@peichenhu
Copy link

peichenhu commented Jul 5, 2021

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

@wangShengCool
Copy link

  function match(arr, target) {
    let index = 0;
    let res = [];
    for (let i = 0; i <= arr.length; ++i) {
      if (index >= arr.length) {
        return;
      }
      if (index !== i) {
        if (arr[index] + arr[i] === target) {
          res.push(arr[index], arr[i]);
          return res;
        } else {
          index++;
        }
      }
    }
    return res;
  }
  这是我的答案,如有欠缺,欢迎各位大佬指正~

@gogopaner
Copy link

`let nums = [1, 2, 3, 4, 5, 6, 7, 11, 15];
let target = 9;
let c = 0;
let list = [];

    function search(one, two = null) {
        for (let i = c; i < nums.length; i++) {
            if (i < nums.length - 1) {
                two = nums[(i + 1)];
                if (one + two === target) {
                    list = [c, i + 1]
                    break;
                } else {
                    if (i === nums.length - 2) {
                        c += 1;
                        search(nums[c]);
                    }
                }
            }
        }
        return list

    }

    console.log(search(nums[c]), 'search()search()');`

@523451928
Copy link

var twoSum = function(nums, target) {
  const obj = {}
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    if (num in obj) {
      return [obj[num], i]
    } else {
      obj[target - num] = i
    }
  }
};

@xiangfei1
Copy link

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]

@mygod48
Copy link

mygod48 commented Oct 28, 2021

使用Map,记录目前已经遍历过的数字中,达到target所需要的“另一半”数字的值,以及对应的“原配”索引。
Map结构:{key: “另一半”数字的值, value: “原配”索引}
遍历时,首先检测是否已经存在“另一半”,如果存在就直接返回记录的“原配”索引,以及当前迭代的数组下标。
如果没有,则计算当前数字所需要的“另一半”,与当前数组下标一同记录在Map中。

由于是先检测是否匹配再添加新键值对,所以不会出现indexOf检测中 arr = [4] 可以达成 target = 8的情况,也不需要额外进行检测。

function sumofTwo(arr, target) {
    const needMap = new Map();

    for (let i = 0; i < arr.length; i++) {
        const num = arr[i];

        if(needMap.has(num)) {
            return [needMap.get(num), i];
        }

        const needNum = target - num;
        needMap.set(needNum, i);
    }

    return [];
}

sumofTwo([2, 7, 11, 15], 9);

@yaoocheng
Copy link


        function findNum(arr, num) {
            let res = [];
            for (let i = 0; i < arr.length; i++) {
                for (let j = 0; j < arr.length; j++) {
                    if(arr[i] == arr[j] && i == j) {
                        continue
                    }
                    if (num - arr[i] == arr[j]) {
                        res.push(i, j);
                        console.log(res)
                        return res
                    }
                }
            };
        }
        findNum(arr, num)

@hdsuperman
Copy link

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);

@AAA611
Copy link

AAA611 commented Nov 26, 2021

function fn1(nums, target) {
let map = Object.create(null)
for (let i = 0; i < nums.length; i++) {
let val = nums[i]
if (map[val] !== undefined) {
return [map[val], i]
} else {
map[target - val] = i
}
}
}

@SnailOwO
Copy link

 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());

@fenglizhu
Copy link

function result(list, target) {
    let map = {};
    let result = []
    for (let i = 0; i < list.length; i++) {
        let reduce = target - list[i];
        if(reduce > 0) map[list[i]] = i;
        if(map.hasOwnProperty(reduce)){
            result.push(map[reduce], i)
            break
            // 如果想要查找所有的,去掉break,执行下面的
            result.push([map[reduce], i])
        }
    }
    return result
}

@Four-Names
Copy link

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];
  }
};

@sexnmaa
Copy link

sexnmaa commented Mar 21, 2022

Map, 空间换时间

var twoSum = function(nums, target) {
    let map = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [i, map.get(target - nums[i])]
    }
    map.set(nums[i], i)
  }
};

@jok-ashun
Copy link

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));

@Vera1128
Copy link

Vera1128 commented Apr 12, 2022 via email

@liushan-github
Copy link

function getTwo(target, arr) {
  for (let i = 0; i < arr.length; i++) {
    const first = arr[i];
    const second = arr[i + 1];
    if (first + second === target) {
      return [i, i + 1]
    }
    if (i === arr.length - 1) {
      return '没有找到'
    }
  }
}

console.log(getTwo(10, [4, 2, 4, 6, 8, 20]))

@523451928
Copy link

function twoSum(nums, target) {
  const obj = {}
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] in obj) {
      return [obj[nums[i]], i];
    } else {
      obj[target - nums[i]] = i;
    }
  }
}

@Vera1128
Copy link

Vera1128 commented Jun 8, 2022 via email

@hzfvictory
Copy link

利用空间换时间:

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 [];
}

twoNum([1,2,3,4,5,6],7) 输出 【2,3】

@Vera1128
Copy link

Vera1128 commented Jul 6, 2022 via email

@tanjunfeng
Copy link

let nums = [2, 7, 11, 15, 17, 25]
let target = 36
let list = []
nums.forEach((v, index) => {
if (nums.includes(target - v)) {
list.push(index, nums.findIndex(j => j === target - v))
}
})
console.log([...new Set(list)])

@benzhemin
Copy link

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);

@gz281620758
Copy link

gz281620758 commented Apr 19, 2023

function sumInArr(arr, target) {
let res = []
for (let i = 0; i < arr.length; i++) {
for (let j = arr.length - 1; j > 0; j--) {
if (arr[i] + arr[j] == target&&i<j) {
res.push(i, j)
break
}
}
}
return res
}
sumInArr([2, 7, 11, 15], 9)
如何评论

@qifengla
Copy link

function twoSum(nums, target) {
  const hashMap = new Map();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (hashMap.has(complement)) {
      return [hashMap.get(complement), i];
    }
    hashMap.set(nums[i], i);
  }

  return []; // 如果不存在符合条件的两个数,则返回空数组
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment