LeetCode 第 1 题

题目：Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly\ one solution, and you may not use the same element twice.

Example:

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

对于我这种不能灵活运用数据结构、没有算法基础的笨🐦来说，遇到涉及到列表的题，第一想到的就是双重循环（甚至多重循环 😅）；上来就要写：

const twoSum(nums, target) = () => {
  let result = [];
  for (let i = 0; i < nums.length; i++) {
    result = [i];
    const first = nums[i];
    const delt = target - first;
    for (let j = i + 1; j < nums.length; j++) {
      const second = nums[j];
      if (second === delt) {
        result.push(j);
        break;
      }
    }
    if (result.length === 2) {
      break;
    }
  }
  return result;
}

写完自己就会感觉很Low，从脑子中仅有的几种数据结构中寻求其他方案；

双重循环👎的话，那就找单次循环的方案，即O(n)复杂度的，两个值相加得target，双因子变化，只能先定下一个因子，才可以找到另一个满足条件的因子。

首先单层循环，可以先找到一个暂时的因子，即 i，找到了暂时的因子，那另一个就好找了，值为target - nums[i]的索引就是另一个因子了。要记得我们的第一个因子是假设为第一个因子的，假设第一个因子的情况下找到了第二个因子，说明假设是对的，也就是一次性得到了结果；但如果假设第一个因子的情况下，没能得到值为target - nums[i]的第二个因子，说明第一个因子就是不满足条件的，这时可以反过来把第二个因子假设为满足条件的第一个因子，再依次上面的推理，找出满足条件的第二个；若再不满足，则继续寻找，直到找到（题目说了假设给定列表一定存在解。> You may assume that each input would have exactly\ one solution）

So，想到了用同时存储key和value来判断 假设的条件是否满足：

var twoSum = function(nums, target) {
    const result = []
    for (let i = 0; i < nums.length; i++) {
        const current = nums[i];
        const delt = target - current;
        if (result.length && result[0].value === delt) {
            return [result[0].key, i]
        }
        result.push({key: i, value: current})
    }
};

然后看了下Solution中的代码，找到了异曲同工的Hash方案，高啊

const twoSum(nums, target) = () => {
  const hash = {};
  for (let i = 0; i < nums.length; i++) {
    const current = nums[i];
    const delt = target - current;
    if (hash.hasOwnProperty(delt)) {
      return [hash[delt], i];
    }
    hash[current] = i;
  }
}