[数据结构与算法]我理解的算法 - 经典题目两数之和

这道题目是乐扣的第一题，非常的经典呢，想必大家要入算法，肯定会先做这道题目，题目内容大家自行查看：链接在这 ，需要从数组中找出2个数的和与目标数字相等的结果，返回2个数在数组中的下标

这道题目有多种解法，最先能想到的暴力法比较简单，嵌套两个for循环搞定，时间复杂度$O(n^2)$，

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

但题目要求我们尝试更快的解法，时间复杂度小于 $O(n^2)$，那么就要想一下了，常用的方式是使用空间换时间，我们可以利用一个HashMap，利用HashMap搜索的时间复杂度为$O(1)$的特性，来降低时间复杂度，从而使我们的算法达到$O(n)$的时间复杂度，另外我们使用HashMap后，我们就可以存储一个当前值与目标值的差值进去，如下代码

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

    return null;
}

每次判断target与当前值的差值是否在map中，如果不存在则将当前值放入map，如果存在则返回当前值的数组下标与map中存入的key值对应的value值即数组下标值为最终结果，至于为什么可以这么做？我们分析一下：

题目要求的是$a+b=c$的解，如果c为target，a为当前for循环的nums[i]，b为差值，我们可以看成是$c?a=b$，因此我们可以把题解看成是在我们的hashMap中寻找让等式能够成立的a，即$c??=b$我们一开始map中肯定是没有值的，因为我们知道$c?a=b$ 等于了$c?b=a$，所以我们将a存入进去这样下次遍历的时候，这时候a就充当了b，那么只要继续找a，就能找出结果来了，也是很巧妙的一种写法。

所以根据上面的解释，也可以这样来写，是一样的

for(int i = 0;i < nums.length; i++){
    if(tempMap.containsKey(nums[i])){
        return new int[]{tempMap.get(nums[i]), i};
    }
    tempMap.put(target - nums[i], i);
}

其实就是利用了$c?a=b$ 等于 $c?b=a$这一特性来实现的这一算法，这样你们理解了么。

接下来我们会研究乐扣15题的三数之和，会给出一种双指针的解法，当然也同样适用这道题目，并且我们会做一些两数之和的变种题目，如乐扣167题，也是使用双指针的解法来做，大家可以自己先去做做看哈

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生