也许是我太菜了,我连最简单的算法题都没过
原题是这样的:
原题地址: https://leetcode-cn.com/problems/two-sum/
乍一看是道非常简单的题目吧
:) 然而并不是
在最开始,我也曾想着用暴力法快速解决,给出了如下代码:
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;
}
}
在一般的情况下,这个可以轻松过关,然鹅....
LeetCode给了一个变态的测试参数: 给你传一个极大的数组,每个数组的下标都是10000 (也就是数组中有大量重复元素) ,然后因为暴力法超时,我就挂了
:(
看来得换思路了
为了对付这种变态的参数,必须得整点Java特有的了:
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.containsKey(target - nums[i])) {
return new int[] {map.get(target-nums[i]),i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
没错,就是集合,用一个Key-Value的Map来解决这个问题
根据题目,每种输入只对应一个答案,且元素不重复使用,可得:
- 如果有3个或者以上的重复元素,代表这个重复元素不可能是解,所以写入map的时候直接覆盖也无所谓
- 如果只有两个重复元素,同样的道理,假如这个重复元素是解,那么必定是两个重复元素的和等于tag
通过上述两点,这种方法得以实现的原因自然就呈现在眼前了~
总结:
暴力法永远不是我们应该去追求的,想办法优化,找出其中可能会有的细节错误才是硬道理,考虑一定要周全!
Q.E.D.
Comments | 0 条评论