《LeetCode刷题》——1.两数之和
@[toc]
一、题目内容
原题连接：https://leetcode.cn/problems/two-sum/
题目：
默认代码模块：
class Solution {
public int[] twoSum(int[] nums, int target) {
}
}二、个人答案（Java）
思路：题目要求是给一个整型的数组和目标值，判断数组中的那两个元素相加等于目标值，再把这两个数的脚标放进一个数组里面，返回这个数组，我想到的是for循环一下子就可以解决，相当于假设给定一串数，12345，遍历一下他们两两组合是否等于目标值，不能重复，就是1分别和后面的数字2345匹配，然后2又和2后面的数字345匹配......以此类推，匹配到了和等于目标值就放进一个数组里面，返回该目标值即可。没有匹配到就返回null
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i <nums.length ; i++) {
for (int j = i+1; j < nums.length; j++) {
if (nums[i]+nums[j]==target){
int[] ints = new int[]{i,j};
return ints;
}
}
}
return null;
}
}三、官方答案（Java）
ps：官方给的方法一也是for循环
方法二如下(官方答案，已备注出处)：
思路及算法
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N)O(N) 降低到 O(1)O(1)O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
代码
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];
}
}作者：LeetCode-Solution
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
