LeetCode每日一题Day3——1. 两数之和

命运之光

发布于 2024-03-20 12:54:19

1230

发布于 2024-03-20 12:54:19

文章被收录于专栏：我在本科期间写的文章

1. 两数之和

正确代码

方法一：暴力搜索

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        
        // 方法一：暴力搜索
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) { // 注意这里是从i+1开始，避免重复利用同一个元素
                if (target - nums[j] == nums[i]) {
                    result.push_back(i);
                    result.push_back(j);
                    return result; // 找到符合条件的两个索引后，直接返回结果
                }
            }
        }
        
        return result; // 如果没有找到结果，则返回空的vector
    }
};

方法二：哈希表求解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numIndexMap; // 哈希表，用于存储元素值与对应的索引

        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i]; // 计算目标值与当前元素的差值

            // 查找差值在哈希表中是否存在，若存在，则找到了符合条件的两个索引
            if (numIndexMap.count(complement) > 0) {
                return {numIndexMap[complement], i};
            }

            // 将当前元素及其索引添加到哈希表中
            numIndexMap[nums[i]] = i;
        }

        return {}; // 如果没有找到结果，则返回空的vector
    }
};

错误总结

第一次提交出现的错误

执行结果

Line 13: Char 5: error: non-void function does not return a value [-Werror,-Wreturn-type] } ^ 1 error generated.

错误原因

代码有一个错误，编译器提示是“non-void function does not return a value”，意思是非void类型的函数必须返回一个值。

在你的代码中，函数twoSum声明的返回类型是vector<int>，但是在函数体内并没有明确指定返回值。这是因为在你的暴力搜索方法中，只是通过cout输出结果，而没有返回任何值。

为了修复这个错误，你应该在函数的末尾返回一个合适的vector<int>类型的值，即找到符合条件的两个索引值，并将它们放入一个vector中后返回。

以下是修复后的代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        
        // 方法一：暴力搜索
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) { // 注意这里是从i+1开始，避免重复利用同一个元素
                if (target - nums[j] == nums[i]) {
                    result.push_back(i);
                    result.push_back(j);
                    return result; // 找到符合条件的两个索引后，直接返回结果
                }
            }
        }
        
        return result; // 如果没有找到结果，则返回空的vector
    }
};

再次提交（成功通过）

但显然暴力搜索只能击败12.97%的对手，不是很好。

尝试对算法进行优化

暴力搜索虽然简单，但是时间复杂度较高，为O(n^2)。我们可以通过使用哈希表来优化算法，将时间复杂度降低为O(n)。下面是优化后的代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numIndexMap; // 哈希表，用于存储元素值与对应的索引

        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i]; // 计算目标值与当前元素的差值

            // 查找差值在哈希表中是否存在，若存在，则找到了符合条件的两个索引
            if (numIndexMap.count(complement) > 0) {
                return {numIndexMap[complement], i};
            }

            // 将当前元素及其索引添加到哈希表中
            numIndexMap[nums[i]] = i;
        }

        return {}; // 如果没有找到结果，则返回空的vector
    }
};