第 86 题：算法题之「两数之和」

Question

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Answer 1

//  the first solution

const twoSum0 = (arr, target) => {

    for(let i = 0; i < arr.length - 1; i ++) {

        for(let j = i + 1; j < arr.length; j ++) {

            if( arr[i] + arr[j] === target ) {

                return [i, j];
            }
        }
    }
}
console.log(twoSum0([1, 4, 5, 8, 7], 8));

// the second solution

const twoSum1 = (arr, target) => {

    let map = {}, res;

    arr.map((item, index) => {

        'undefined' !== typeof map[target - item] ? res = [map[target - item], index] : map[item] = index;
    });

    return res;
}
console.log(twoSum1([1, 4, 5, 8, 7], 8));

// the third solution 出现第一个时直接return出去，性能更好

const twoSum = ( arr, target ) => {

    let map = {}, res;

    for(let i = 0; i < arr.length; i ++) {

        if( 'undefined' !== typeof map[target - arr[i]] ) {

            return [ map[target - arr[i]], i ];
        }
        map[ arr[i] ] = i;
    }
}

Answer 2

function sum(nums, target){

for(let i = 0; i < nums.length; i ++) {

	let indexL = nums.indexOf(target - nums[i], i + 1)

	if(indexL !== -1){

		return [i, indexL]

	}

}

}

Answer 3

let nums = [2,7,11,15]
const func = (nums, target) => {
  if (!Array.isArray(nums) || typeof target !== 'number') throw '错误的数据'
  nums = Array.from(nums)
  let indexs = []
  let index = nums.length - 1
  while(nums.length && !indexs.length) {
    const num = nums.pop()
    const alias = target - num
    const aliasIndex = nums.indexOf(alias)
    if (~aliasIndex) indexs.push(aliasIndex, index)
    index--
  }
  return indexs
}

Answer 4

function test(num,target){
    for(let i=0;i<num.length-1;i++){
        if(num[i]<= target){
	    for(let j=i+1;j<num.length;j++){
	        if(num[j]<=target && num[i]+num[j] === target){
		    return [i,j];
		}
	    }
	}
    }
    return [];
}

Answer 5

一个哈希表一趟循环就可以了

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

Answer 6

Answer 7

var twoSum = (nums, target) => {
  // 一趟哈希表
};

var twoSum2 = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    const left = nums[i];
    let copyNums = nums.slice(i + 1);
    let rightIndex = copyNums.indexOf(target - left);

    if (rightIndex !== -1) {
      return [i, rightIndex + i + 1];
    }
  }
};

var twoSum3 = function (nums, target) {
  var _result;
  nums.some(function (item, index) {
    var _index = nums.indexOf(target - item);
    if (_index !== -1 && index !== _index) {
      _result = [index, _index];
      return true;
    }
  });
  return _result;
};

Answer 8

时间复杂度o(2n)吧， 借助HASH查找， 空间复杂度也差了些

function findTarget(nums, target) {
	const map = {}
	for (let i = 0, len = nums.length; i < len; i++) {
		map[target - nums[i]] = i + 1
  }
  console.log(map);
	for (let i = 0, len = nums.length; i < len; i++) {
		if (map[nums[i]]) {
			return [i, map[nums[i]] - 1]
		}
	}
	return []
}

Answer 9

• 利用哈希表
• 时间复杂度 O(n)，空间复杂度O(n)

function toSum(nums, target) {
  var map = {}
  for (let i = 0; i < nums.length; i++) {
    var n = target - nums[i]
    if (n in map) {
      return [map[n], i]
    } else {
      map[nums[i]] = i
    }
  }
  return []
}

var nums = [2, 7, 11, 15]
var target = 9

console.log(toSum(nums, target)) // [0, 1]

Answer 10

排序 + 二分，时间复杂度O(nlogn)。

Answer 11

leetcode第一题

var twoSum = function(nums, target) {
  var cache_dic = {}
  for (let i in nums) {
      var y = target - nums[i]
      if (cache_dic[y]) {
          return [cache_dic[y], i]
      }
      cache_dic[nums[i]] = i
  }
};

Answer 12

var arr = [2,7,11,15];
var target = 9;
var result = [];

arr.forEach(function(valOut,indexOut,selfOut){
	let arrRest = selfOut.slice(indexOut+1);
	arrRest.forEach(function(valIn,indexIn,selfIn){
		if(valOut+valIn===target){
			result.push(indexOut);
			result.push(indexOut+indexIn+1);
		}
	});
});

console.log(result);

Answer 13

思路一：暴力破解法

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (i !== j && nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

由于进行了双重循环，时间复杂度是O(n^2), 空间复杂度O(1)

思路二：两趟哈希表

function twoSum(nums, target) {
  const map = {}
  for (const [i, n] of nums.entries()) {
    map[n] = i
  }
  for (const [i, n] of nums.entries()) {
    let number = target - n
    if (number in map) {
      return [i, map[number]]
    }
  }
}

• 先用一个哈希表存储数组的值于对应数组下标，然后再遍历数组寻找结果
• 时间复杂度O(n), 空间复杂度O(n)

思路三：一趟哈希表

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

• 在给哈希表添加元素的同时寻找有没有符合目标的答案，如果有就直接返回，没有就继续构造哈希表。
• 时间复杂度O(n), 空间复杂度O(n)

第二种思路可能有点问题，当数组内容都是重复的内容例如twoSum([2,2,2,2],4)

Answer 14

var nums = [1,-5,33,4,66,6,7,8];
var target = 9;
var pos = [];
for(var i=0; i<nums.length-1; i++){
var current = nums[i];
var index = i;
for(var j=i+1; j<nums.length; j++){
if(nums[j] + current === target){
pos.push(i, j);
}
}
}

Answer 15

let arr1 = [1, 2, 3, 7, 8, 10];
let arr2 = [];
let target = 9;
arr1.map((item, index) => {
if(index < (arr1.length-2)) {
for(var i = index;i<arr1.length;i++){
if((item+arr1[i]) == target) {
arr2.push([index, i])
}
}
}
})

Answer 16

function findIndexArr(nums,target){
for(let i=0; i<nums.length;i++){
var index = nums.slice(i+1).indexOf(target-nums[i])
if(index!==-1){
return [i,index+i+1]
}
}
}
每次遍历当前index后的数组部分，找到后，返回index,和index后数组中匹配的元素的位置

Answer 17

function twoSum(arr=[],target){
			for (var i = 0,len = arr.length; i < len; i++) {
				let num = target - arr[i]
				let index = arr.findIndex(function(value) {
					return value === num
				})
				if( index > -1){
					return [i,index]
				}
			}
		}

Answer 18

/**

• @param {number[]} nums
• @param {number} target
• @return {number[]}
  */
  var twoSum = function(nums, target) {
  for(let i = 0; i < nums.length; i++){
  var num_one = target - nums[i]
  for(let j = i + 1; j < nums.length; j++){
  if(num_one === nums[j]){
  return new Array(i, j)
  }
  }
  }
  };

Answer 19

// 暴力破解法
function findTowOfSum(nums, target) {
  let i, j;

  for (i = 0; i < nums.length; i++) {
    for (j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }

  return null;
}

// 数组反查法
function findTowOfSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    let j = nums.indexOf(target - nums[i]);

    if (j > 0) {
      return [i, j];
    }
  }

  return null;
}

Answer 20

思路一：暴力破解法

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (i !== j && nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

由于进行了双重循环，时间复杂度是O(n^2), 空间复杂度O(1)

思路二：两趟哈希表

function twoSum(nums, target) {
  const map = {}
  for (const [i, n] of nums.entries()) {
    map[n] = i
  }
  for (const [i, n] of nums.entries()) {
    let number = target - n
    if (number in map) {
      return [i, map[number]]
    }
  }
}

• 先用一个哈希表存储数组的值于对应数组下标，然后再遍历数组寻找结果
• 时间复杂度O(n), 空间复杂度O(n)

思路三：一趟哈希表

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

• 在给哈希表添加元素的同时寻找有没有符合目标的答案，如果有就直接返回，没有就继续构造哈希表。
• 时间复杂度O(n), 空间复杂度O(n)