本文共 1223 字，大约阅读时间需要 4 分钟。

解决方案：使用哈希表来优化查找过程，时间复杂度为O(n)

问题描述

给定一个整数数组，找到两个数的索引，使得它们的和等于一个特定的目标值。每个输入都有一个唯一的解，且不能使用同一个元素两次。

解决方法

为了高效地解决这个问题，我们可以使用哈希表（字典）来优化查找过程。哈希表允许我们在常数时间内查找特定值，这将使得整体时间复杂度降低到O(n)，其中n是数组的长度。

方法思路

代码实现

#include 
   
    #include 
    
     using namespace std;class Solution {public:    vector
     
       twoSum(vector
      
        nums, int target) {        unordered_map
       
         hmap;        for (int i = 0; i < nums.size(); ++i) {            int input = nums[i];            int key = target - input;            if (hmap.find(key) != hmap.end()) {                return {hmap[key], i};            }            hmap[input] = i;        }        return {};    }};
       
      
     
    
   

代码解释

• 初始化哈希表：unordered_map<int, int> hmap; 用于存储数值及其对应的索引。
• 遍历数组：for (int i = 0; i < nums.size(); ++i) 遍历每个元素。
  • 计算关键码：int key = target - nums[i]; 计算目标减去当前元素的值。
  • 查找关键码：if (hmap.find(key) != hmap.end()) 检查哈希表中是否存在该关键码。
    • 找到配对：如果存在，返回哈希表中对应的值和当前索引。
    • 存入哈希表：如果不存在，将当前数值及其索引存入哈希表。
• 返回结果：一旦找到配对，立即返回结果，减少不必要的计算。

这种方法确保了在最佳时间复杂度内解决问题，适用于大规模数据。

转载地址：http://dyir.baihongyu.com/