文章目錄
- 題目 [兩數之和](https://leetcode.cn/problems/two-sum/)
- 方法一：暴力枚舉
- 代碼
- 方法二：哈希表
- 代碼
- 哈希表
- 哈希表的基本概念
- 哈希函數（Hash Function）：
- 沖突（Collision）：
- 鏈地址法（Chaining）：
- 開放地址法（Open Addressing）：
- 哈希表的操作
- 插入（Insert）：
- 查找（Search）：
- 刪除（Delete）：
- 哈希表的優點和缺點
- 優點：
- 缺點：
- 基本用法
- 示例代碼
- 示例 1：計數字符出現次數
- 示例 2：兩數之和問題
- 注意事項
- 性能
- 哈希函數
- 內存開銷
題目 兩數之和
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，并返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。
你可以按任意順序返回答案。
方法一：暴力枚舉
思路及算法
最容易想到的方法是枚舉數組中的每一個數 x，尋找數組中是否存在 target - x。
當我們使用遍歷整個數組的方式尋找 target - x 時，需要注意到每一個位于 x 之前的元素都已經和 x 匹配過，因此不需要再進行匹配。而每一個元素不能被使用兩次，所以我們只需要在 x 后面的元素中尋找 target - x。
代碼
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (nums[i] + nums[j] == target) {return {i, j};}}}return {};}
};
復雜度分析
時間復雜度：O(N2)，其中 N 是數組中的元素數量。最壞情況下數組中任意兩個數都要被匹配一次。
空間復雜度：O(1).
方法二：哈希表
思路及算法
注意到方法一的時間復雜度較高的原因是尋找 target - x 的時間復雜度過高。因此，我們需要一種更優秀的方法，能夠快速尋找數組中是否存在目標元素。如果存在，我們需要找出它的索引。
使用哈希表，可以將尋找 target - x 的時間復雜度降低到從 O(N) 降低到 O(1)。
這樣我們創建一個哈希表，對于每一個 x，我們首先查詢哈希表中是否存在 target - x，然后將 x 插入到哈希表中，即可保證不會讓 x 和自己匹配。
代碼
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashtable;for (int i = 0; i < nums.size(); ++i) {auto it = hashtable.find(target - nums[i]);if (it != hashtable.end()) {return {it->second, i};}hashtable[nums[i]] = i;}return {};}
};復雜度分析
時間復雜度：O(N)，其中 N 是數組中的元素數量。對于每一個元素 x，我們可以 O(1) 地尋找 target - x。
空間復雜度：O(N)，其中 N 是數組中的元素數量。主要為哈希表的開銷。
哈希表
哈希表的基本概念
哈希函數（Hash Function）：
- 哈希函數將輸入的鍵轉換為哈希碼，這個哈希碼通常是一個整數。
- 哈希碼用于確定鍵值對在哈希表中的存儲位置。
- 一個好的哈希函數應當均勻地分布鍵，減少沖突的發生。
沖突（Collision）：
- 當兩個不同的鍵被哈希函數映射到同一個存儲位置時，稱為沖突。
- 處理沖突的方法主要有兩種：鏈地址法（Chaining）和開放地址法（Open Addressing）。
鏈地址法（Chaining）：
- 每個存儲桶存儲一個鏈表或其他數據結構來處理沖突。
- 當沖突發生時，新鍵值對被插入到對應存儲桶的鏈表中。
開放地址法（Open Addressing）：
- 當沖突發生時，尋找另一個空的存儲桶來存儲沖突的鍵值對。
- 常見的開放地址法包括線性探測（Linear Probing）、二次探測（Quadratic Probing）和雙重散列（Double Hashing）。
哈希表的操作
插入（Insert）：
- 計算鍵的哈希碼，找到對應的存儲桶。
- 如果沒有沖突，直接插入。
- 如果有沖突，根據沖突解決策略進行處理（例如鏈地址法或開放地址法）。
查找（Search）：
- 計算鍵的哈希碼，找到對應的存儲桶。
- 在存儲桶中查找鍵值對。
- 如果使用鏈地址法，可能需要遍歷鏈表。
刪除（Delete）：
- 計算鍵的哈希碼，找到對應的存儲桶。
- 在存儲桶中查找并刪除鍵值對。
- 如果使用鏈地址法，可能需要遍歷鏈表。
哈希表的優點和缺點
優點：
- 快速查找、插入和刪除： 平均情況下，這些操作的時間復雜度都是 O(1)。
- 實現簡單： 相對于平衡樹等復雜數據結構，哈希表的實現較為簡單。
缺點：
- 需要處理沖突： 盡管沖突不可避免，但沖突處理機制（如鏈地址法或開放地址法）會影響性能。
- 內存消耗： 哈希表通常需要額外的內存來存儲鏈表或解決沖突，這在存儲空間有限的情況下可能是個問題。
- 無法有序遍歷： 哈希表中的元素沒有特定順序，因此不能按順序遍歷所有鍵值對。
基本用法
在C++中，unordered_map 是標準庫（STL）中的一種關聯容器，提供了鍵值對的哈希表實現。下面是一些常見的操作：
- 引入頭文件
#include <unordered_map>
- 在使用 unordered_map 之前，需要引入 <unordered_map> 頭文件。
- 聲明一個哈希表
std::unordered_map<int, int> hashtable;
- 聲明一個鍵為 int，值也為 int 的哈希表。
- 插入元素
hashtable[1] = 100;
hashtable.insert({2, 200});
- 使用 [] 操作符或 insert 方法插入鍵值對。
- 訪問元素
int value = hashtable[1];
auto it = hashtable.find(2);
if (it != hashtable.end()) {std::cout << "Found: " << it->second << std::endl;
}
- 使用 [] 操作符訪問元素或使用 find 方法查找元素。
- 刪除元素
hashtable.erase(1);
- 使用 erase 方法刪除鍵值對。
- 遍歷哈希表
for (const auto& pair : hashtable) {std::cout << pair.first << ": " << pair.second << std::endl;
}
使用范圍 for 循環遍歷哈希表中的所有鍵值對。
示例代碼
下面是一些具體示例，展示如何使用 unordered_map：
示例 1：計數字符出現次數
#include <unordered_map>
#include <iostream>
#include <string>int main() {std::string str = "hello world";std::unordered_map<char, int> char_count;// 統計每個字符出現的次數for (char c : str) {if (c != ' ') {char_count[c]++;}}// 輸出字符出現的次數for (const auto& pair : char_count) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}
示例 2：兩數之和問題
#include <unordered_map>
#include <vector>
#include <iostream>std::vector<int> twoSum(const std::vector<int>& nums, int target) {std::unordered_map<int, int> hashtable;for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i];auto it = hashtable.find(complement);if (it != hashtable.end()) {return {it->second, i};}hashtable[nums[i]] = i;}return {};
}int main() {std::vector<int> nums = {2, 7, 11, 15};int target = 9;std::vector<int> result = twoSum(nums, target);if (!result.empty()) {std::cout << "Indices: " << result[0] << ", " << result[1] << std::endl;} else {std::cout << "No solution found." << std::endl;}return 0;
}
注意事項
性能
unordered_map提供平均 O(1) 的插入、查找和刪除操作，但在最壞情況下，這些操作可能是 O(n) 的。- 哈希表的性能高度依賴于哈希函數的質量和負載因子（元素數量與桶的數量之比）。
哈希函數
- 自定義類型作為鍵時，需要提供自定義的哈希函數和相等函數。
內存開銷
unordered_map在存儲鍵值對時會使用額外的內存來維護哈希桶。
)
