【LeetCode Hot 100】两数之和

鸠羽芊叶 發表於 2025-5-15 09:17:00

<h1 id="两数之和">两数之和</h1>
题目链接：LeetCode 两数之和
<h2 id="题目描述">题目描述</h2>
给定一个整数数组 <code>nums</code> 和一个整数目标值 <code>target</code>，请你在该数组中找出和为目标值 <code>target</code>的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
示例1:
<pre><code>输入：nums = , target = 9
输出：
解释：因为 nums + nums == 9 ，返回。
</code></pre>
示例 2：
<pre><code>输入：nums = , target = 6
输出：
</code></pre>
示例 3：
<pre><code>输入：nums = , target = 6
输出：
</code></pre>
进阶要求:将时间复杂度从$\mathcal{O}(n^2)$降低到$\mathcal{O}(n)$。
<h2 id="解题思路与代码">解题思路与代码</h2>
题目给出了一个一维数组和一个目标值, 想要从数组中找到两个不相同的和为这个目标值的数字，设数组为 
$A = \{a_0,a_1,\cdots,a_{n-1}\}$ ，目标值为 $b$，从数组$$A$$ 中找到两个值 $a_i , a_j$，满足以下条件：
<div class="math display">\[b = a_i + a_j ,\;\;\; 0\leq i\neq j\leq n-1.
\]</div>能想到，分配两个指针 $i$ 和 $j$ 在数组 $A$ 中分别遍历，每走一步即检查是否与 $b$ 相等且要避免指向相同位置，时间复杂度为 $\mathcal{O}(n^2)$。
<pre><code class="language-cpp">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 {};
}
};
</code></pre>
我们可以从另一个角度来考虑。因为 $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)$。
<pre><code class="language-cpp">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};
}
};
</code></pre>
<h2 id="扩展">扩展</h2>
在上面两段代码实现中，都可以看到在返回值时直接返回一个包含数据的花括号（解法1：第7、12行；解法2：第12行）。 
函数的返回类型 <code>vector<int></code>可以按初始化列表初始化容器，得益于<code>vector</code>提供了一个接受初始化列表的构造函数，其签名如下：
<pre><code class="language-cpp">template <typename T>
std::vector<T>::vector(std::initializer_list<T> init);
</code></pre>
这个构造函数接受一个 <code>std::initializer_list<T></code> 类型的参数，其中 <code>T</code> 是 <code>std::vector</code> 的元素类型。<code>std::initializer_list</code> 是一个轻量级的容器，它提供了一种方便的方式来表示初始化列表。 
来源：https://www.cnblogs.com/vvital/p/18877128

頁: [1]

琼殿技术论坛's Archiver

【LeetCode Hot 100】两数之和