【LeetCode Hot 100】两数之和

两数之和

题目链接：LeetCode 两数之和
题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，而且你不能使用两次雷同的元素。你可以按恣意顺序返回答案。
示例1:

1. 输入：nums = [2,7,11,15], target = 9
2. 输出：[0,1]
3. 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

复制代码

示例 2：

1. 输入：nums = [3,2,4], target = 6
2. 输出：[1,2]

复制代码

示例 3：

1. 输入：nums = [3,3], target = 6
2. 输出：[0,1]

复制代码

进阶要求:将时间复杂度从\(\mathcal{O}(n^2)\)降低到\(\mathcal{O}(n)\)。
解题思绪与代码

题目给出了一个一维数组和一个目标值, 想要从数组中找到两个不雷同的和为这个目标值的数字，设数组为
\(A = \{a_0,a_1,\cdots,a_{n-1}\}\) ，目标值为 \(b\)，从数组$$A$$ 中找到两个值 \(a_i , a_j\)，满足以下条件：

\[b = a_i + a_j ,\;\;\; 0\leq i\neq j\leq n-1.\]
能想到，分配两个指针 \(i\) 和 \(j\) 在数组 \(A\) 中分别遍历，每走一步即检查是否与 \(b\) 相等且要避免指向雷同位置，时间复杂度为 \(\mathcal{O}(n^2)\)。

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.         for (int i = 0 ; i < nums.size() ; i++) {
5.             for (int j = 0 ; i != j && j < nums.size() ; j++) {
6.                 if ( nums[i] + nums[j] == target)
7.                     return {i,j};      
8.                 else
9.                     continue;
10.             }
11.         }
12.         return {};
13.     }
14. };

复制代码

我们可以从另一个角度来考虑。因为 \(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)\)。

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.         unordered_map<int,int> mp;
5.         for (int i = 0 ; i < nums.size() ; i++)
6.         {
7.             auto it = mp.find(nums[i]);
8.             if ( it != mp.end())
9.                 return {it->second , i};
10.             mp[target-nums[i]] = i;
11.         }
12.         return {-1,-1};
13.     }
14. };

复制代码

扩展

在上面两段代码实现中，都可以看到在返回值时直接返回一个包含数据的花括号（解法1：第7、12行 ； 解法2：第12行）。
函数的返回类型 vector可以按初始化列表初始化容器，得益于vector提供了一个担当初始化列表的构造函数，其署名如下：

1. template <typename T>
2. std::vector<T>::vector(std::initializer_list<T> init);

复制代码

这个构造函数担当一个 std::initializer_list 类型的参数，其中 T 是 std::vector 的元素类型。std::initializer_list 是一个轻量级的容器，它提供了一种方便的方式来表示初始化列表。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。