|
1 | 1 | <palign="center"> |
2 | 2 | <ahref="https://mp.weixin.qq.com/s/TsTcCDboXwnTnUeIW3Zg9Q"><imgsrc="https://img.shields.io/badge/LeetCode组队刷题群-blueviolet"alt=""></a> |
3 | 3 | </p> |
| 4 | + |
| 5 | +##0001-Two-Sum-两数之和.md |
| 6 | +https://leetcode-cn.com/problems/two-sum/ |
| 7 | + |
| 8 | +##题意 |
| 9 | + |
| 10 | +给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 |
| 11 | + |
| 12 | +你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 |
| 13 | + |
| 14 | +你可以按任意顺序返回答案。 |
| 15 | + |
| 16 | +**样例** |
| 17 | + |
| 18 | +```txt |
| 19 | +输入：nums = [2,7,11,15], target = 9 |
| 20 | +输出：[0,1] |
| 21 | +解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 |
| 22 | +``` |
| 23 | + |
| 24 | + |
| 25 | +##题解 |
| 26 | + |
| 27 | +哈希可以快速查找一个数字。 |
| 28 | + |
| 29 | +建立哈希表，key等于数组的值，value等于值所对应的下标。 |
| 30 | + |
| 31 | +然后遍历数组，每次遍历到位置`i`时，检查`target-num[i]` 是否存在，注意`target-num[i]`的位置不能等于`i`。 |
| 32 | + |
| 33 | +下图以示例演示一下哈希表，将数组插入到哈希表中，查找给定的`key`，即可以在`O(1)` 的时间复杂度查找到，图中的a、b、c、d指的是哈希表的索引。 |
| 34 | + |
| 35 | + |
| 36 | + |
| 37 | +##Java代码 |
| 38 | + |
| 39 | +```java |
| 40 | +classSolution { |
| 41 | +publicint[]twoSum(int[]nums,inttarget) { |
| 42 | +HashMap<Integer,Integer> numExist=newHashMap<Integer,Integer>(); |
| 43 | +for (int i=0; i< nums.length;++i) { |
| 44 | +if (numExist.containsKey(target- nums[i])) { |
| 45 | +returnnewint[]{i, numExist.get(target- nums[i])}; |
| 46 | + } |
| 47 | + numExist.put(nums[i], i); |
| 48 | + } |
| 49 | +returnnewint[2]; |
| 50 | + } |
| 51 | +} |
| 52 | +``` |
| 53 | + |
| 54 | +##C++代码 |
| 55 | + |
| 56 | +```c++ |
| 57 | +classSolution { |
| 58 | +public: |
| 59 | + unordered_map<int, int> numExist; |
| 60 | + vector<int> twoSum(vector<int> &nums, int target) { |
| 61 | + vector<int> ans; |
| 62 | + for (int i = 0; i < nums.size(); i++) { |
| 63 | + int b = target - nums[i]; |
| 64 | + if (numExist.count(b)) { |
| 65 | + ans.push_back(i); |
| 66 | + ans.push_back(numExist.at(b)); |
| 67 | + break; |
| 68 | + } |
| 69 | + numExist[nums[i]] = i; |
| 70 | + } |
| 71 | + return ans; |
| 72 | + } |
| 73 | +}; |
| 74 | +``` |