Leetcode 1：两数之和
题目：两数之和
难度：easy
知识点：暴力、哈希表
俗话说，万事开头难，第一道题当然是要写一下leetcode的第一题啊！
解法1
很容易想到的有个方法就是暴力解决，也很简单，不断地遍历，时间复杂度为O(n^2)，直接上代码吧。
1
2
3
4
5
6
7
8
9
10
11
12
| 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){
return new int[]{i,j};
}
}
}
return null;
}
}
|
解法2
我们可以增加一个备忘录的功能，一旦发现备忘录中存在我们正在找的元素，那么直接返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
| 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(nums[i])) {
return new int[]{hashtable.get(nums[i]), i};
}
hashtable.put(target - nums[i], i);
}
return new int[0];
}
}
|
以上就是两种不同的方法了。
