LeetCode热题100：两数之和的两种解法

在LeetCode中，两数之和（Two Sum）是一道非常热门的题目。这道题目要求在给定的整数数组中找到两个数，使它们的和等于给定的目标值。以下是这个问题的两种常见解法：暴力枚举和哈希表。
解法一：暴力枚举
暴力枚举是一种简单直接的解法，通过两层循环枚举数组中的所有可能数对，然后判断它们的和是否等于目标值。如果相等，则返回这两个数的下标。
示例代码（C语言）：

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
int i, j;
for (i = 0; i < numsSize; i++) {
for (j = i + 1; j < numsSize; j++) {
if (nums[i] + nums[j] == target) {
int* result = (int*)malloc(sizeof(int) * 2);
result[0] = i;
result[1] = j;
*returnSize = 2;
return result;
}
}
}
*returnSize = 0;
return NULL;
}

这种解法的时间复杂度为O(n^2)，在数组较大时效率较低。因此，我们还可以使用哈希表来优化算法。
解法二：哈希表
哈希表是一种数据结构，可以在常数时间内完成查找操作。我们可以使用哈希表来存储数组中的每个元素以及它的下标，然后在遍历数组时查找目标值的另一半。
示例代码（C++）：

#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++) {
if (hashTable.find(target - nums[i]) != hashTable.end()) {
vector<int> result = {hashTable[target - nums[i]], i};
return result;
}
hashTable[nums[i]] = i;
}
return {};
}

在这个示例中，我们使用unordered_map作为哈希表，存储数组中的每个元素以及它的下标。在遍历数组时，我们检查目标值减去当前元素是否在哈希表中，如果在，则返回这两个数的下标。否则，我们将当前元素和它的下标存入哈希表中。最终，如果没有找到符合条件的数对，则返回一个空数组。
这种解法的时间复杂度为O(n)，其中n是数组的大小。它比暴力枚举更加高效，特别是对于较大的数组。在实际应用中，我们通常会优先选择哈希表解法来解决两数之和的问题。