LeetCode 1. Two Sum 两数之和

📜 Description 题面

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

You may assume that each input would have exactly one solution, and you may not use the same element twice.

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

🔗 Link 链接

LeetCode: https://leetcode.com/problems/two-sum/

力扣：https://leetcode-cn.com/problems/two-sum/

❓ Solution 题解

Approach 1: Brute Force 暴力

The brute force approach is simple. Loop through each element x and find if there is another value that equals to target-x.

暴力法很简单，遍历每个元素 x，并查找是否存在一个值与 target-x 相等的目标元素。

Complexity Analysis 复杂度分析

• Time complexity : O(n^2)
• 时间复杂度：O(n^2)

For each element, we try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2).

对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n^2)。

• Space complexity : O(1)
• 空间复杂度：O(1)

Approach 2: One-pass Hash Table 一遍哈希表

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

• Time complexity : O(n)
• 时间复杂度：O(n)

We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.

我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。

• Space complexity : O(n)
• 空间复杂度：O(n)

The extra space required depends on the number of items stored in the hash table, which stores at most n elements.

所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

📝 Code 代码

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> res;

		for (int i = 0; i < nums.size(); i++)  // 按照题意遍历所有元素，查找和是否与target相等 
			for (int j = i + 1; j < nums.size(); j++)
				if (nums[i] + nums[j] == target)
					return vector<int> {i, j};
		return res;
	}
};

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> res;
		unordered_map<int, int> mp;  // unordered_map是哈希表而map是红黑树 

		for (int i = 0; i < nums.size(); i++) {
			int iComplement = target - nums[i];  // 计算当前数的补数 
			if (mp.count(iComplement)) return vector<int> {mp[iComplement], i};  // 当前数是补数，返回结果{补数下标, 当前数下标} 
			mp.insert({ nums[i], i });  // 当前数不是补数，向哈希表内插入当前数和下标 
		}
		return res;
	}
};