Leetcode 1. Two Sum

Two Sum :

題意是給一個名為nums的array，array中的兩個值加起來等於target，如果存在的話，返回那兩個值所在的陣列位置。

此題利用dictionary的特性來求解，第一次掃描array，將所有的數重新存放到一個dict中，將dict以原數組中的值為鍵；第二次掃描array，對於每個數nums[i]查看target-nums[i]是否在dict中，若存在則可得到答案。

時間複雜度: O(n)

空間複雜度: O(1)

Python

class Solution(object):
    def twoSum(self, nums, target):
        dict={}
        for i in range(len(nums)):
            if target-nums[i] in dict:
                return [dict[target-nums[i]],i]
            if nums[i] not in dict:
                dict[nums[i]]=i

C++

for迴圈直接找target

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

哈希表，把值都先放入哈希表(tmp)，再把target減掉每個nums的值得到cur，如果哈希表tmp包含cur且沒重複的數，則返回答案

class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> tmp;
    for (int i = 0; i < nums.size(); ++i)
      tmp[nums[i]] = i;
    
    for (int i = 0; i < nums.size(); ++i) {
      int cur = target - nums[i];
      if (tmp.count(cur) && tmp[cur] != i) {
          return {i, tmp[cur};
      }
    }
    return {};
  }
};