---
title: 'Leetcode 第1題 題解 — C++'
disqus: hackmd
---

# Leetcode 第1題 題解 — C++
:::info
:bulb: 此筆記為Leetcode 第 1 題的題目詳解，包含解題思路、C++範例程式碼。
:::

## 1. [Two Sum](https://leetcode.com/problems/two-sum/)

### 解題思路
:::warning
建立一個unordered_map作為哈希表。
遍歷0 ~ 最後在nums中的數值，並將已搜尋到的值存入哈希表（key為該位置的索引值）。
每一次遍歷都會令target - 該索引值在nums中的數值為complement，並用unordered_map的find找出哈希表中以complement為key的數值（unordered_map[complement]，此處時間複雜度為O(1)）。
:::

### 範例程式碼

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i;
        unordered_map<int, int> hash;

        for (i=0;i<nums.size();i++) {
            int complement = target - nums[i];

            if (hash.find(complement) != hash.end())  //如果hash[complement]存在
                return {i, hash[complement]};
            
            hash[nums[i]] = i;  //用hash[nums[i]] = i表示nums[i]這個值在nums中的位置為i
        }

        return {};
    }
};

### 運行結果
**Time Complexity**: O(n)
**Space Complexity**: O(n)
**Runtime**:
1 ms | Beats 83.67%
**Memory**:
14.74 MB | Beats 41.11%

###### tags: `LeetCode Easy`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::