------------------------
- 涉及内容：
- 哈希
- 2020/10/16
题目如下：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
补充知识点：
哈希表：https://www.cnblogs.com/cstrick-1/p/13824940.html
实现：
- 解法①：暴力枚举，二重循环
-----------------------------------------------------------
- 参数说明：
- 时间复杂度：O（N^2）
- 空间复杂度：O（1）
-----------------------------------------------------------
`
C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
`
- 解法②：借助哈希表实现
------------------------------------------------------------
------------------------------------------------------------
- 函数说明：
- 具体看最后的演算过程
- hashtable.containsKey()比较的是键值，键值也就是哈希表表中存储的数据
- hashtable.get()返回指定键所映射到的值，也会是数组的值
- hashtable.put(Object key, Object value) 将指定 key 映射到此哈希表中的指定 value。
- 时间复杂度：O（N）
- 空间复杂度：O（N）
------------------------------------------------------------
Java
`
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) { // 和哈希表中的值进行比较，若存在，则返回
return new int[] {hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
`
-----------------------------------------------------------------------------------------------------------
- 演算过程：假设nums[2,7,11,25] target=18
通过hashtable.containsKey()函数进行比较键值，键值也就是哈希表表中存储的数据
containsKey(target - nums[0] ) 此处比较的是哈希表里面是否存在18 - 2 = 16 ， 如果表中存在16，那么就
说明哈希表中的 16 和 要入表的 2 刚好可以是题目所要求的解。如果哈希表中不存在16，则将2入表。依次类推
-----------------------------------------------------------------------------------------------------------
C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
if (m.count(target - nums[i])) {
return {i, m[target - nums[i]]};
}
m[nums[i]] = i;
}
return {};
}
};
哈希表主要是对暴力枚举的第二重循环进行优化，用空间换时间。