题目 — 两数之和
做法1: O($n^2$)
暴力枚举每两个数
如果下标不同,且相加 == target ,则记录答案直接返回
代码如下
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> res;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j && nums[i] + nums[j] == target)
{
res.push_back(i);
res.push_back(j);
return res;
}
return res;
}
};
做法2: O($n$)
暴力枚举每两个数
如果下标不同,且相加 == target ,则记录答案直接返回
因为两`个数的总和是一定的,== target, 所以依次遍历每个数时,与之相匹配的数也是确定的,== target - nums[i]
我们记录每个数的下标,如果一个数出现多次,我们记录它最靠后的下标
依次遍历每个数 每次找到它应该匹配的数, target - nums[i], 如果它之前被记录过,则直接返回
为什么记录每个数字靠后的下标:
解释:因为我们枚举的时候,是从前到后后枚举,如果这个元素在数组中存在多个,当我们枚举到它的时候一定是第一次出现的位置可以直接将存储的位置加入到答案中,直接返回
注意: 数组中同一个元素在答案里不能重复出现,如果 nums[i] == target - nums[i] && nums[i]只出现一次,也是不合法的,只需要判断 i != 记录的下标 即可
代码如下
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> ump;
int n = nums.size();
for (int i = 0; i < n; i++)
ump[nums[i]] = i + 1;
vector<int> res;
for (int i = 0; i < n; i++)
{
int t = target - nums[i];
if (ump.count(t) && ump[t] - 1 != i)
{
res.push_back(i);
res.push_back(ump[t] - 1);
break;
}
}
return res;
}