week1-leetcode #1-Two Sum[Easy]

leetcode #1-Two Sum[Easy]

Question

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 = [, , , ], target = ,

Because nums[] + nums[] =  +  = ,
return [, ].
           

Solution1[base]

time complecity: O(n2)

space complecity: O(n)

runtime:132ms

#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      int num_size = nums.size();
      vector<int> return_vec;
      for (int i = ; i < num_size; i++) {
        for (int j = i+; j < num_size; j++) {
          int num1 = nums[i];
          int num2 = nums[j];
          if (target == num1+num2) {
            return_vec.push_back(i);
            return_vec.push_back(j);
            return return_vec;
          }
        }
      }
      return return_vec;
    }
};
           

思路：使用雙重循環周遊vector，第一重循環确定第一個數字，第二重循環确定第二個數字，複雜度是 O(n)∗O(n)=O(n2) 。

Solution2[optimal]

time complecity: O(n)

space complecity: O(n)

runtime:9ms

#include <vector>
#include <iostream>
// #include <ctime>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      unordered_map<int, int> hash_map;
      const int nums_size = nums.size();
      vector<int> return_vec;
      for (int i = ; i < nums_size; i++)
        hash_map[nums[i]] = i;
      for (int i = ; i < nums_size; i++) {
        int num_to_find = target-nums[i];
        // 找到了
        if (hash_map.find(num_to_find) != hash_map.end() && hash_map[num_to_find] != i) {
          return_vec.push_back(i);
          int j = hash_map[num_to_find];
          return_vec.push_back(j);
          break;
        }
      }
      return return_vec;
    }
};
           

思路：使用一個哈希表來存儲每個值對應的索引資訊。使用兩次一重循環，第一次是建立哈希表，複雜度是 O(n) 。第二次是在哈希表中尋找特定數字，複雜度是 O(1)∗O(n)=O(n) 。總複雜度是 O(n)+O(n)=O(n) 。