也许是我太菜了,我连最简单的算法题都没过

原题是这样的:

原题地址: 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.