C++ 两数之和算法优化：查找目标值的下标

C++ 两数之和算法优化：查找目标值的下标

问题:

给定一个整数数组 nums 和一个目标值 target，找出 nums 中的两个数，使得它们的和等于 target。

原始代码:

vector<int> twoSum(vector<int>& nums, int target){
    int n=nums.size();
    vector<int> ans(2);
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(nums[i]+nums[j]==target) {
                ans[0]=nums[i],ans[1]=nums[j];
                return ans;
            }else if(nums[i]+nums[j]>target) break;
        }
    }
}

问题分析:

该函数只是找到了两个数的和等于目标值的情况，但题目要求返回这两个数的下标。需要对代码进行修改。

优化方案:

1. 使用哈希表存储数字及其下标。
2. 遍历数组，对于每个数字，在哈希表中查找目标值与当前数字差值的对应下标。
3. 如果找到，则返回当前数字的下标和差值的对应下标。

优化后的代码:

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.count(complement)) {
            return {hashTable[complement], i};
        }
        hashTable[nums[i]] = i;
    }
    return {}; // 如果没有找到，返回空向量
}

代码说明:

1. 使用 unordered_map 存储数字和其下标的对应关系。
2. 遍历数组，对于每个数字 nums[i]，计算其补数 complement = target - nums[i]。
3. 在哈希表中查找补数是否存在，如果存在，则返回补数的下标和当前数字的下标。
4. 如果不存在，则将当前数字及其下标存储到哈希表中，继续遍历。

总结:

通过使用哈希表，可以将查找目标值对应数字的时间复杂度从 O(n^2) 降低到 O(n)，有效提升了算法效率。