LeetCode 1. 两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target ,请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
示例1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例3：
输入：nums = [3,3], target = 6
输出：[0,1]
算法1
（暴力枚举）
O
(
n
2
)
O(n^{2})
O(n2)
两重循环枚举下标
i
i
i ,
j
j
j，然后判断
n
u
m
s
[
i
]
+
n
u
m
s
[
j
]
nums[i] + nums[j]
nums[i]+nums[j] 是否等于
t
a
r
g
e
t
target
target。
class Solution {
public:
vectorint> twoSum(vectorint>& nums, int target) {
vectorint> res;
for (int i = 0; i nums.size(); i ++ ) {
for (int j = 0; j i; j ++ ) {
if (nums[i] + nums[j] == target) {
res = vectorint>({j, i});
break;
}
}
if (res.size() > 0) break;
}
return res;
}
};
算法2
（哈希表）
O
(
n
服务器托管 )
O(n)
O(n)
使用C++ STL中的哈希表——unordered_map hash.
每次枚举第二个数
s
i
s_i
si ，找这个数的前面有没有一个值为
t
a
r
g
e
t
−
s
i
target – s_i
target−si 的数，如果有则返回这两个数的下标。
具体做法：
-
开一个哈希表，遍历数组
n
u
m
s
nums
nums，扫描
n
u
m
s
[
i
]
nums[i]
nums[i] 时，说明已经把
n
u
m
s
[
i
]
nums[i]
nums[i] 前面的所有数存入到了哈希表中。
-
每次遍历时，首先判断哈希表中有没有
t
a
r
g
e
t
−
n
u
m
s
[
i
]
target – nums[i]
target−nums[i]，如果有则为答案，若没有则将当前元素
n
u
m
s
[
i
]
nums[i]
nums[i] 插入到哈希表中。
-
时间复杂度：由于只扫描一遍，且哈希表的插入和查询操作的复杂度是
O
(
1
)
O(1)
O(1).
class Solution {
public:
vectorint> twoSum(vectorint>& nums, int target) {
unordered_mapint, int> hash; //服务器托管 定义一个哈希表，将每个数的数值映射到下标
for (int i = 0; i nums.size(); i ++ ) {
int r = target - nums[i];
if (hash.count(r)) return {hash[r], i};
hash[nums[i]] = i;
}
return {};
}
};
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
