两数之和 - 越走越远的风

欢迎关注个人公众号【好好学技术】交流学习

前言

算法对程序员而言重要吗？

图灵奖获得者，Pascal之父尼克劳斯·维尔特曾经说过：程序 = 数据结构 + 算法。

其实编程从本质上来说就是算法加上数据结构。

然而现实生活中大部分工作很少会直接用到算法或数据结构，多数都是写CRUD或处理业务逻辑。即使完全不懂算法和数据结构，也可以把工作做好。

所以对于初入门的程序员来说，算法和数据结构似乎是可有可无的。很多人算法的巅峰水平可能就是大学毕业的时候，随着工作年限增长，不常用的算法与数据结构知识基本就忘光了。

但是矛盾的是面试中常常会碰到算法和数据结构。

其实在成为一个高级程序员，甚至架构师的路上，算法是非常非常重要的一环。好的算法可以化繁为简，解决一系列复杂的问题。

我曾经很多次强迫自己去学习算法，刷题。但是很遗憾，每次都是坚持一两天就放弃了。所以希望在这里能够坚持下去，每天坚持练习算法。

也希望大家能够每天花费五分钟和我一起坚持，成长。

不积跬步，无以至千里；不积小流，无以成江海

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1.暴力法

看到一道题目往往首先第一思路是暴力法，然后在考虑能否优化。
暴力法其实很简单，将数组两两相加，计算他们的和是否和target一致，如果是就输出，否则继续循环。

    /**  
     * 暴力破解  
     *  
     * @param nums   数组  
     * @param target 两数之和目标值  
     * @return 两数的数组下标  
     */  
    private static int[] twoSum1(int[] nums, int target) {
        //双层for循环遍历 时间复杂度 O(n的平方)
        for (int i = 0; i < nums.length; i++) {
            //数组中同一个元素在答案里不能重复出现
            for (int j = i + 1; j < nums.length; j++) {
                //两数之和为target
                if (nums[j] + nums[i] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
     }

这种方法虽然简单，但是缺点也是明显的，嵌套for循环，时间复杂度为O(n^2)。

2.遍历两次数组

为了对时间复杂度进行优化。我们可以考虑将所有数据放到map里面去，key为数组的值，value为该值的下标。
那么我们只需要对nums数组进行一次for循环，然后查看map的key是否包含target - nums[i]即可。

    /**  
     * 遍历两次数组  
     *  
     * @param nums   数组  
     * @param target 两数之和目标值  
     * @return 两数的数组下标  
     */  
    private static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            //key 为数组的值     value 存放数组下标
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            /**
             * 设 x = target - nums[i]  就等于  num[i] + x = target
             * 然后判断 x 这个值是否在 map中，即 map.containsKey(x)
             *
             * 题目要求 数组中同一个元素在答案里不能重复出现
             * map.get(x) != i  防止同一下标计算两次，  如目标值是8，  nums[2] = 4 , 则会返回 4,4
             */
            int x = target - nums[i];
            if (map.containsKey(x) && map.get(x) != i) {
                return new int[]{i, map.get(target - nums[i])};
            }
        }
        return null;
    }

这种方法从时间复杂度考虑，已经变为O(n)了。但是for循环了两次，还是有改进的空间的。

3.遍历一次数组

其实我们完全可以一次for循环，就将所需的结果取出。
题目中已说明：数组中同一个元素在答案里不能重复出现。那么我们可以定义一个map，key为数组的值，value为该值的下标。
for循环遍历数组，然后查看map是否包含key为target - nums[i]的元素。
如果包含直接返回结果，否则将该元素的值和下标放入map即可。

    /**  
     * 遍历一次数组  
     *  
     * @param nums   数组  
     * @param target 两数之和目标值  
     * @return 两数的数组下标  
     */  
    private static int[] twoSum3(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            //如果map存在 x 则直接返回结果,否则将当前值和下标保存在 map中
            if (map.containsKey(x)) {
                return new int[]{map.get(x), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }

时间复杂度还是O(n)，但是相对第二种，只进行了一次for循环。

源码地址

https://github.com/fandf/algorithm/blob/master/src/main/java/com/fandf/algorithm/TwoSum.java

最后

千里之，行始于足下，每天坚持一点

如果大家有更好的解法或者疑问，欢迎留言一起交流学习。