大家好,又见面了,我是你们的朋友全栈君。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> twoSum;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if((nums[i]+nums[j])==target){
twoSum.push_back(i);
twoSum.push_back(j);
}
}
}
return twoSum;
}
};
复杂度分析:
O(n2), 对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费
O(n)O(n)O(n)的时间。因此时间复杂度为
O(n2)。
O(1)。
//C++ hash_map 用法示例:
#include <map>
#include <string>
using namespace std;
map<string, string> namemap;
//增加。。。
namemap["岳不群"]="华山派掌门人,人称君子剑";
namemap["张三丰"]="武当掌门人,太极拳创始人";
namemap["东方不败"]="第一高手,葵花宝典";
//查找。。
if(namemap.find("岳不群") !=namemap.end()){ ...}
–哈希表:
//哈希表
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> twoSum;
map<int, int> tmpmap;//键值为nums的值,变量值为nums下标
for (int i = 0; i < nums.size(); i++) {
tmpmap[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i++) {
if (tmpmap.count(target - nums[i]) != 0 && tmpmap[target-nums[i]]!=i) {// 如果目标值减去循环到的值对应的下标不为0,或者不为i,【存在有另一个数与循环值相加等于target,则返回结果】
twoSum.push_back(i);
twoSum.push_back(tmpmap[target - nums[i]]);
break;
}
}
return twoSum;
}
–哈希表优化版:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> twoSum;
map<int, int> tmpmap;//键值为nums的值,变量值为nums下标
for (int i = 0; i < nums.size(); ++i) {
if (tmpmap.count(nums[i]) != 0) {
twoSum.push_back(tmpmap[nums[i]]);
twoSum.push_back(i);
break;
}
tmpmap[target - nums[i]] = i;
}
return twoSum;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136472.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...