LeetCode：两数之和——哈希表解法详解
LeetCode 是一个全球知名的在线编程社区，提供了大量的编程题目，旨在帮助程序员提升算法和数据结构能力。其中，“两数之和”是 LeetCode 上的一道经典题目，旨在考察我们对哈希表的理解和应用。本文将围绕这一主题，从多种编程语言的角度，详细解析哈希表在解决两数之和问题中的应用。
题目描述
给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。你不能重复利用这个数组中同样的元素。
哈希表解法
哈希表（Hash Table）是一种基于散列原理的数据结构，它通过散列函数将键映射到表中的位置，从而实现快速查找。在解决两数之和问题时，我们可以利用哈希表来存储数组中已经遍历过的元素及其对应的索引，从而在常数时间内检查是否存在与当前元素相加等于目标值的另一个元素。
Python 实现
python
def twoSum(nums, target):
hash_table = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_table:
return [hash_table[complement], i]
hash_table[num] = i
return []
示例
nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target)) 输出: [0, 1]
Java 实现
java
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hashTable = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (hashTable.containsKey(complement)) {
return new int[]{hashTable.get(complement), i};
}
hashTable.put(nums[i], i);
}
return new int[0];
}
// 示例
int[] nums = {2, 7, 11, 15};
int target = 9;
System.out.println(Arrays.toString(twoSum(nums, target))); // 输出: [0, 1]
JavaScript 实现
javascript
function twoSum(nums, target) {
let hashTable = {};
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (hashTable.hasOwnProperty(complement)) {
return [hashTable[complement], i];
}
hashTable[nums[i]] = i;
}
return [];
}
// 示例
let nums = [2, 7, 11, 15];
let target = 9;
console.log(twoSum(nums, target)); // 输出: [0, 1]
C++ 实现
cpp
include <vector>
include <unordered_map>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashTable;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (hashTable.find(complement) != hashTable.end()) {
return {hashTable[complement], i};
}
hashTable[nums[i]] = i;
}
return {};
}
// 示例
vector<int> nums = {2, 7, 11, 15};
int target = 9;
cout << vector<int>{twoSum(nums, target)[0], twoSum(nums, target)[1]} << endl; // 输出: [0, 1]
总结
本文从多种编程语言的角度，详细解析了哈希表在解决两数之和问题中的应用。通过哈希表，我们可以在常数时间内检查是否存在与当前元素相加等于目标值的另一个元素，从而有效地解决了这个问题。在实际编程中，熟练掌握哈希表及其应用场景，将有助于我们解决更多类似的问题。
Comments NOTHING