Two Sum问题是大多数刷LeetCode的小伙伴们遇到的第一个问题。下面我将从三个方面为各位小伙伴们讲述Two Sum问题。
1、Two Sum问题的描述和解法
2、哈希表的原理及其应用
3、由Two Sum问题扩展的其他问题的解题思路
1、Two Sum问题的描述。
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。[1]
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路一：
这个问题最容易想到的思路就是，由两个索引循环遍历nums数组，遍历所有可能的两个数字的组合，如(2, 7), (2, 11), ······ (11, 15)。然后，对组合里的数字求和，判断这个和是否等于target，如果相等，则将这两个整数所对应的下标输出。
这个思路的算法复杂度是O(n^2)。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
size_t len = nums.size();
bool is_found = false;
vector<int> result;
for (int i = 0; i < len; i++) {
for (int j = i+1; j < len; j++) {
if (nums[i] + nums[j] == target)
{
result.push_back(i);
result.push_back(j);
is_found = true;
}
if (is_found)
break;
}
if (is_found)
break;
}
return result;
}
};
思路二：
另外一种方法是，借助哈希表良好的查询性能，可以将时间复杂度压缩到O(n)。也就是说，遍历一次数组，就能找到在数组中和为目标值的两个数字的下标。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
size_t len = nums.size();
vector<int> result;
unordered_map<int, int> data;
for (size_t i = 0; i < len; i++) {
if (data.find(nums[i]) == data.end()) {
data[target – nums[i]] = i;
}
else {
result.push_back(data[nums[i]]);
result.push_back(i);
break;
}
}
return result;
}
};
2、哈希表的原理及其应用
在解决Two Sum问题的过程中，用到了哈希表。
此处顺便简单讲述一下哈希表，方便各位小伙伴了解一些原理性的内容。
哈希表是一种能够快速存取的数据结构。存的时间复杂度是O(1)，取的时间复杂度也是O(1)。存取都可以在常量时间内完成。
要构建一个哈希表，主要由两个步骤（散列函数、碰撞冲突）：
第一个步骤：使用散列函数将被查找的键转化为数组的一个索引。
第二个步骤：当两个或多个键映射到相同的数组索引时，需要使用一些方法去解决碰撞冲突这个问题。常用的解决碰撞冲突的方法：拉链法和线性探测法。
有关哈希表的详细内容，如哈希表的散列函数一般有哪些、拉链法和线性探测法是如何工作的等内容，请参考相关博文。
3、由Two Sum问题扩展的其他问题的解题思路
Two Sum问题可以进一步扩展成Three Sum问题。
稍后将附上由Two Sum问题扩展出来的问题的解法。