【LeetCode Hot 100】两数之和
两数之和题目链接：LeetCode 两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
示例1:
输入：nums = , target = 9
输出：
解释：因为 nums + nums == 9 ，返回 。示例 2：
输入：nums = , target = 6
输出：示例 3：
输入：nums = , target = 6
输出：进阶要求:将时间复杂度从\(\mathcal{O}(n^2)\)降低到\(\mathcal{O}(n)\)。
解题思路与代码
题目给出了一个一维数组和一个目标值, 想要从数组中找到两个不相同的和为这个目标值的数字，设数组为
\(A = \{a_0,a_1,\cdots,a_{n-1}\}\) ，目标值为 \(b\)，从数组$$A$$ 中找到两个值 \(a_i , a_j\)，满足以下条件：
\
能想到，分配两个指针 \(i\) 和 \(j\) 在数组 \(A\) 中分别遍历，每走一步即检查是否与 \(b\) 相等且要避免指向相同位置，时间复杂度为 \(\mathcal{O}(n^2)\)。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for (int i = 0 ; i < nums.size() ; i++) {
for (int j = 0 ; i != j && j < nums.size() ; j++) {
if ( nums + nums == target)
return {i,j};
else
continue;
}
}
return {};
}
};我们可以从另一个角度来考虑。因为 \(b\) 是定值，分配一个指针 \(i\) 遍历数组 \(A\)，那么数组 \(A\)被分为了两个部分（已经遍历过的部分和未遍历的部分），当指针 \(i\)每指向一个未遍历部分的数时，都查看已经遍历过的部分是否有 \(a_j =b-a_i\) ，能这样做的原因得益于题目说明 \(a_i \neq a_j\)。
如何查找一段序列 \(\{a_0,a_1,\cdots,a_{i-1}\}\) 是否包含某值且要做到时间复杂度低，可以考虑哈希表，哈希表在查找键值的时间复杂度为 \(\mathcal{O}(1)\)，算法时间复杂度将为 \(\mathcal{O}(n)\)。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> mp;
for (int i = 0 ; i < nums.size() ; i++)
{
auto it = mp.find(nums);
if ( it != mp.end())
return {it->second , i};
mp] = i;
}
return {-1,-1};
}
};扩展
在上面两段代码实现中，都可以看到在返回值时直接返回一个包含数据的花括号（解法1：第7、12行 ； 解法2：第12行）。
函数的返回类型 vector可以按初始化列表初始化容器，得益于vector提供了一个接受初始化列表的构造函数，其签名如下：
template <typename T>
std::vector<T>::vector(std::initializer_list<T> init);这个构造函数接受一个 std::initializer_list 类型的参数，其中 T 是 std::vector 的元素类型。std::initializer_list 是一个轻量级的容器，它提供了一种方便的方式来表示初始化列表。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]