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
}
};
再接再厉,继续加油!