1. 两数之和

题目要求

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

“

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

”

题解

1、暴力循环

两次遍历。
第一次遍历，分别拿出第i个参数，
第二次遍历，分别拿出后边的所有参数j，与i对比，判断求和是否为目标值。

时间复杂度：O(n^2)
空间复杂度：O(1)

function towSum(nums, target) {
  let result = []
  if (Array.isArray(nums) && typeof target === 'number') {
    for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
        if (nums[i] + nums[j] === target) {
          result.push([
            [nums[i], nums[j]],
            [i, j]
          ])
        }
      }
    }
  }
  return result
}

let result = towSum([1, 2, 3, 14, 11, 13, 21, 4, 23], 24)
console.log(result)
/* 结果：
[ [ [ 1, 23 ], [ 0, 8 ] ],
  [ [ 3, 21 ], [ 2, 6 ] ],
  [ [ 11, 13 ], [ 4, 5 ] ] ] */

2、优化求解

设置一个对象，映射i与target的差值为对象的key，value为i。

时间复杂度：O(n)
空间复杂度：O(1)

function towSum2(nums, target) {
  if (!nums || !Array.isArray(nums)) return
  let len = nums.length, differMap = {}
  for (let i = 0; i < len; i++) {
    let curNum = nums[i]
    if (differMap[curNum] !== undefined) return [i, differMap[curNum]]
    differMap[target - curNum] = i
  }
}
let result2 = towSum2([1, 2, 3, 14, 11, 13, 21, 4, 23], 24)
console.log(result2)

• 用一个对象，键为当前值和目标值的差，值为当前值的下标。
• 对象结构伪代码：{ target - nums[i] : i };
• 在仅有的一次循环中，如果对象的key等于当前遍历数组的值，说明当前数组的值就是之前遍历值与target的差。
• 即以对象key对应的value值为下标，该下标所在数组中的对应值，和当前遍历的值之和是target。
• 所以，对象key对应的value与当前遍历的i（数组下标）就是要找的那俩下标。