1. Two Sum

Leetcode link

解题思路——O(n^2)

这是一道简单题，一个最直接的解题思路就是用双循环：外侧循环输入数组，内侧循环寻找target - nums[i]的差，如果找到就把两个下标装到一个数组中返回出去。

注：在 JS 中的 indexOf 本质上也是用了遍历O(n)

C++

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
      int remains = target - nums[i];
      for (int j = i + 1; j < nums.size(); j++) {
        if (nums[j] == remains) {
          result.push_back(i);
          result.push_back(j);
          return result;
        }
      }
    }
    return result;
  }
};

Javascript

var twoSum = function(nums, target) {
    for(let i=0;i<nums.length;i++) {
        let remains = target - nums[i];
        let idx = nums.indexOf(remains)
        if(idx !== -1 && idx !== i) {
            return [i, idx]
        }
    }
    return [];
};

解题思路——O(n)

想当然尔，一个简单题用了 O(n^2)的算法复杂度，不只是题目最下面的 Follow-up 不满意，面试官也肯定不满意🐶

所以就有了空间换时间的思路：用一个 map 来保存之前出现过的值以及对应的下标，之后直接用 O(1) 在 map 里找就完事了。

注：JS用了另一种思路，保存了当前下标及当前的值与target的差，但是本质是一样的。

C++

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
      if (map.count(target -
                    nums[i]))  // if target - nums[i] value found in map
        return {i, map[target - nums[i]]};
      else
        map[nums[i]] = i;
    }
    return {};
  }
};

Javascript

var twoSum = function(nums, target) {
    let cache = {};
    for(let i=0;i<nums.length;i++){
        let remains = target - nums[i];
        if(cache[nums[i]] !== undefined){
            return [i,cache[nums[i]]];
        }
        cache[remains] = i;

    }
    return [];
};