An old dog learns code

[LeetCode 1] Two Sum

February 28, 2019


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].

题目类型分析

Two Sum 可以说是 LC 最经典的题目,没做过 Two Sum 甚至都不好意思说自己刷过 LC。每次看到这道题都会想起自己刷题初期的窘迫,百感交集。

这道题没有什么复杂的规则,属于数据结构应用。

解法

  1. 暴力解法

    什么也不想的情况下,第一反应肯定是 brutal force ,2 个 for 循环就完事了。时间复杂度  O(n2)\ O(n^2), 效率实在不高。

    var twoSum = function(nums, target) {
     var res = [];
     for (let i = 0; i < nums.length; i++) {
       for (let j = i + 1; j < nums.length; j++) {
         if (nums[i] + nums[j] == target) {
           res[0] = nums[i];
           res[1] = nums[j];
         }
       }
     }
     return res;
    };
  2. hashmap 两次遍历

    换一个思路,可以用空间来换时间,先遍历数组,在 hashmap 里建立元素索引,然后再遍历数组,在 hashmap 里找对应元素的配对。这样就把时间复杂度降低到了 O(n)\ O(n),当然空间复杂度也提升到了 O(n)\ O(n)

    var twoSum = function(nums, target) {
     var map = {},
       res = [];
     //建立索引
     for (let i = 0; i < nums.length; i++) {
       if (map[nums[i]] == undefined) map[nums[i]] = i;
     }
     //查找配对元素
     for (let i = 0; i < nums.length; i++) {
       let residual = target - nums[i];
       if (map[residual] != undefined && map[residual] != i) {
         res.push(map[residual]);
         res.push(i);
         break;
       }
     }
     return res;
    };
  3. hashmap 一次遍历

    解法 2 当然可以再优化一下,只需要一次遍历就可以找到结果。少了一次遍历,时间复杂度和空间复杂度同上。

var twoSum = function(nums, target) {
  var map = {},
    res = [];
  for (let i = 0; i < nums.length; i++) {
    let curElement = nums[i];
    let residual = target - curElement;
    //找到当前元素的配对
    if (map[residual] !== undefined) {
      res.push(map[residual]);
      res.push(i);
      break;
    }
    //建立元素索引
    map[curElement] = i;
  }
  return res;
};