二数之和
(暴力枚举) $O(n^2)$
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;
}
}
(哈希表做法) $O(n) < X < O(n^2)$
要活学活用哈希表,不要只会死用hash表的映射功能,比如说这道题:
如果 target - nums[i]存在于hash表,说明这两个数相加为target,否则才压入。
两者只需要一个入hash表即可
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i ++) {
if(map.get(target - nums[i]) != null) return new int[]{map.get(target - nums[i]), i};
map.put(nums[i], i);
}
return null;
}
}
代码优化 — 命名优化 + 可读性优化
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i ++ ) {
int complement = target - nums[i];
if(map.containsKey(complement)) return new int[]{map.get(complement), i};
else map.put(nums[i], i);
}
return null;
}
}