算法是思想,数据结构是工具
题目描述
来源:Two Sum
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
算法分析
1. 暴力法
算法描述
两个指针i和j,i从0开始遍历,j从i+1位置开始遍历,如果两个数之和等于target,则返回答案,否则返回空数组
时间复杂度:O(n^2)
代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for(int i = 0; i < n; i ++) {
for(int j = i + 1; j < n; j ++) {
if(nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
2. 哈希表法
算法描述
由暴力法得到启发,对于每一个i,都会有j从i+1开始遍历,则存在元素的重复遍历,因此,使用哈希表记录之前遍历过的元素,一旦出现当前元素与已经遍历过的元素和为target的情况,则返回i和j,否则返回空数组
时间复杂度:O(n)
代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
unordered_map<int, int> record;
for(int i = 0; i < n; i ++) {
if(record.count(target - nums[i])) {
return {i, record[target - nums[i]]};
}
record[nums[i]] = i;
}
return {};
}
};
总结
如果出现暴力解涉及重复遍历,则考虑哈希表做法