两数之和（TwoSum）

大家都说 算法 是程序员的分水岭， 三年 技术一个坎。

我工作2年已经感觉到危机感，正准备同时这面临着两个问题了，不如蹭现在还有来得及一起去把算法练起来吧，光看可不行得练。尽可能的把 https://leetcode-cn.com/ Leetcode 力扣 中的算法题都刷一遍。

遵循：先用自己的可以实现的方法做，做出来后，在看看大佬们的性能解法学习学习。 （连自己的方法都做不出来，只能偷偷的看看答案了xixixi~，不管是白猫黑猫抓到老鼠就是好猫，先要求自己做对，再最求性能）

我也会把 Leetcode 力扣 上做的题目代码，放在 GitHub 上进行同步，方便大家查阅代码，给出你的 Pr 和提出 issues 。

GitHub: https://github.com/aquanlerou/leetcode

两数之和（TwoSum）

首先我们先看看题目描述：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/two-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我第一时间看到题目后想法，逐个逐个循环nums[]相加得出结果后，判断结果是否与 target 相等，相等后就跳出循环，这个估计是最笨的办法了。

• 遍历数组两两相加得出结果

• 循环中判断是否与目标数相等

  • 相等跳出循环，记录数值的位置
  • 不相等继续循环相加

• 最后把记录的数值return返回

上代码：

public int[] twoSum(int[] nums, int target) {    
    int n = nums.length;    
    int a = 0;    
    int b = 0;    
    for(int i=0 ; i <=n; i++) {        
        for(int j=i+1; j<n; j++) {            
            int result = nums[i] + nums[j];            
            if(result == target) {                
                a = i;                
                b = j;            
            }        
        }    
    }    
    int[] resultArray = new int[]{a, b};    
    return resultArray;
}

这种解法，估计就是速度慢和性能上消耗大了。这里我还无法用什么 时间复杂度 和 空间复杂度 去评论，因为我不懂 doge-，-，下面得好好了解下才行了。

Dalao 解法

参考：https://leetcode-cn.com/problems/two-sum/s...

看完解法后，了解到是利用到了HashMap中的containsKey方法查找Map中Key降低耗时。

• 循环遍历

  • 把nums[]中的值已Key形式，和对应值的nums[]的下标已value形式存进Map中
  • 循环中进行target - nums[i]计算
  • 计算结果通过containsKey方法在Map中查找是否有对应值
  • 有的话就返回map.get(target - nums[i])和循环的次数i
  • 我们最后还是得考虑下要是数组中没有对应的结果应该怎么处理，这个时候我们返回-1，-1

代码：

public int[] twoSumHash(int[] nums, int target) {    
    Map<Integer, Integer> map = new HashMap<>();    
    for (int i=0; i<nums.length; i++) {        
        int result = target - nums[i];        
        if (map.containsKey(result)) {            
            return new int[] {map.get(result), i};        
        }        
        map.put(nums[i], i);    
    }
    return new int[] {-1, -1};
}

最后希望大家可以理解得了，可能会描述的不清楚。

本作品采用《CC 协议》，转载必须注明作者和本文链接