跳到主要内容

两数之和

· 阅读需 6 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——1题​

💡 参考代码：​

#include <stdio.h>
#include <stdlib.h>

// 哈希表节点结构
typedef struct HashNode {
    int key;            // 数组元素值
    int value;          // 数组元素索引
    struct HashNode* next;
} HashNode;

// 哈希表结构
typedef struct {
    HashNode** buckets; // 桶数组
    int size;           // 哈希表大小
} HashMap;

// 创建哈希表
HashMap* createHashMap(int size) {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    map->size = size;
    map->buckets = (HashNode**)calloc(size, sizeof(HashNode*));
    return map;
}

// 哈希函数
int hash(HashMap* map, int key) {
    // 处理负数情况
    return abs(key) % map->size;
}

// 向哈希表中添加元素
void put(HashMap* map, int key, int value) {
    int bucketIndex = hash(map, key);
    HashNode* node = map->buckets[bucketIndex];
    
    // 检查是否已存在该key
    while (node != NULL) {
        if (node->key == key) {
            node->value = value; // 更新值
            return;
        }
        node = node->next;
    }
    
    // 创建新节点并插入到链表头部
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = map->buckets[bucketIndex];
    map->buckets[bucketIndex] = newNode;
}

// 从哈希表中获取值
int get(HashMap* map, int key, bool* found) {
    int bucketIndex = hash(map, key);
    HashNode* node = map->buckets[bucketIndex];
    
    while (node != NULL) {
        if (node->key == key) {
            *found = true;
            return node->value;
        }
        node = node->next;
    }
    
    *found = false;
    return -1;
}

// 释放哈希表内存
void freeHashMap(HashMap* map) {
    for (int i = 0; i < map->size; i++) {
        HashNode* node = map->buckets[i];
        while (node != NULL) {
            HashNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(map->buckets);
    free(map);
}

/**
 * 两数之和 - 哈希表解法（进阶解法）
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 * 
 * @param nums 整数数组
 * @param numsSize 数组长度
 * @param target 目标值
 * @param returnSize 返回数组的大小
 * @return 返回两个元素的索引数组
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    // 创建哈希表
    HashMap* map = createHashMap(numsSize);
    
    // 分配返回数组内存
    int* result = (int*)malloc(2 * sizeof(int));
    
    // 遍历数组
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i]; // 计算补数
        bool found = false;
        
        // 在哈希表中查找补数
        int index = get(map, complement, &found);
        
        // 如果找到了补数，返回两个索引
        if (found) {
            result[0] = index;
            result[1] = i;
            *returnSize = 2;
            freeHashMap(map); // 释放哈希表内存
            return result;
        }
        
        // 将当前元素存入哈希表
        put(map, nums[i], i);
    }
    
    // 未找到符合条件的组合（题目保证存在，此行理论上不会执行）
    *returnSize = 0;
    freeHashMap(map);
    return NULL;
}

📖 总结：​

点击展开题目总结

🤔 两数之和

1️⃣ 题目核心信息​

🎯 功能描述：在给定整数数组中找到两个数，使其和等于目标值，并返回这两个数的索引

📥 输入输出：

  • 输入：
    • nums: 整数数组
    • numsSize: 数组长度
    • target: 目标和值
  • 输出：
    • 返回包含两个索引的数组
    • returnSize: 返回数组的大小（设置为2）

2️⃣ 实现原理​

💡 核心思路：使用哈希表存储已遍历元素的值和索引，将查找时间从O(n)降低到O(1)

📋 实现步骤：

  1. 遍历数组中的每个元素
  2. 计算当前元素与目标值的差值（补数）
  3. 在哈希表中查找该补数是否存在
  4. 若存在则返回两个索引，否则将当前元素存入哈希表

3️⃣ 关键点解析​

原始思路是暴力双重循环，时间复杂度O(n²)。哈希表优化后时间复杂度降为O(1)，但需要额外O(n)空间。

🎯 代码技巧​

  • 使用哈希表优化查找时间
  • 边遍历边存储，避免重复计算
  • 合理设计哈希函数处理负数情况

4️⃣ 使用场景​

✅ 适用情况：​

  • 在大数据集中快速查找两数之和
  • 需要频繁进行此类查询的场景
  • 对时间复杂度有较高要求的情况

⚠️ 前提条件：​

  • 输入数组至少包含两个元素
  • 存在唯一解（题目保证）
  • 同一元素不能使用两次

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(1) - 只需遍历数组一次
  • 💾 空间复杂度：O(n) - 哈希表最多存储n个元素

6️⃣ 注意事项​

🚩 边界情况：​

  • 数组中存在负数
  • 目标值为0或负数
  • 数组中存在相同元素

💥 易错点：​

  • 返回数组的内存分配和释放
  • 哈希冲突的处理
  • 未正确设置returnSize参数

7️⃣ 补充说明​

以示例2为例：nums = [3,2,4], target = 6

算法执行步骤演示​

int nums[] = {3, 2, 4};
int target = 6;
int numsSize = 3;
int returnSize;

第1步：初始化​

  • 创建空哈希表
  • 开始遍历数组，i = 0
  • 当前元素：nums[0] = 3
  • 计算补数：complement = target - nums[0] = 6 - 3 = 3
  • 在哈希表中查找3：未找到
  • 将(3, 0)存入哈希表

哈希表现状：​

Key: 3 → Value: 0

第2步：继续遍历​

  • i = 1
  • 当前元素：nums[1] = 2
  • 计算补数：complement = target - nums[1] = 6 - 2 = 4
  • 在哈希表中查找4：未找到
  • 将(2, 1)存入哈希表

哈希表现状：​

Key: 3 → Value: 0
Key: 2 → Value: 1

第3步：找到结果​

  • i = 2
  • 当前元素：nums[2] = 4
  • 计算补数：complement = target - nums[2] = 6 - 4 = 2
  • 在哈希表中查找2：找到，对应索引为1
  • 返回结果：[1, 2]

可视化执行过程​

遍历过程:
┌────────┬────────┬──────────┬────────────┬─────────────────┐
│ 步骤   │ 索引i  │ nums[i]  │ complement │ 哈希表操作      │
├────────┼────────┼──────────┼────────────┼─────────────────┤
│ 1      │ 0      │ 3        │ 3          │ 存入(3,0)       │
│ 2      │ 1      │ 2        │ 4          │ 存入(2,1)       │
│ 3      │ 2      │ 4        │ 2          │ 查找2→找到索引1 │
└────────┴────────┴──────────┴────────────┴─────────────────┘

最终返回: [1, 2]
验证: nums[1] + nums[2] = 2 + 4 = 6 ✓

算法核心思想​

通过哈希表记录"值->索引"的映射关系，将"查找另一个加数"的时间复杂度从O(n)降低到O(1)。整个算法只需一次遍历即可完成，大大提高了效率。

加载评论中...