【算法】LeetCode算法题-Two Sum

佚名 6年前 (2018-10-15) 算法 2010人围观抢沙发百度已收录

程序 = 数据结构 + 算法。

算法是每一位程序员学习成长之路上无法避开的重要一环，并且越早接触越好。今后会每天做些算法题，至少每天做一道题目，同时会记录自己的解题思路和代码，通过【算法】专题来分享。针对数据结构这一块的知识，我也会抽时间补习，毕竟不是科班出生，从长远看，数据结构与算法学的越早越扎实越好，不管你使用的是哪一种开发语言。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

01 看题和准备

给定一个整数数组和一个目标整数，该目标整数满足数组中两元素之和，返回数组中两个数字的下标索引，以数组形式表示结果。例如给定数组int[] nums = [2, 7, 11, 15],目标整数int target = 9,因为 nums[0] + nums[1] = 2 + 7 = 9,返回包含两数索引的数组[0, 1]。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 分析题目

这道题目求的是数组内任意两元素之和等于给定的目标整数，于是很容易想到数组for循环遍历，并且是两层for循环，于是第一版的代码思路已经有了。

public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    if (nums.length < 2) {
        return null;
    }
    try {
        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;
                }
            }
        }
    } catch (Exception e) {
        e.printStackTrace();
        return null;
    }
    return result;
}

03 是否还可以优化？

上面的解法是两层循环，循环次数是n*(n-1)次，n为数组元素个数，n越大，程序执行的时间越长，那能不能只循环一次？既然可以做加法匹配，那做减法呢？先拿到目标整数与数组中每位元素的差值，再去判断此差值是否存在于此数组中。这时，我们需要一个存新数据的集合，既包含每位元素，也包含每位元素的索引，对此选取Map作为存放新数据的对象。

public int[] twoSum2(int[] nums, int target) {
    int[] result = new int[2];
    if (nums.length < 2) {
        return null;
    }
    try {
        Map<Integer, Integer> map = new HashMap<>();
        for (int k=0; k<nums.length; k++) {
            int num = target - nums[k];
            if (map.containsKey(num)) {
                result[0] = map.get(num);
                result[1] = k;
            }
            map.put(nums[k], k);
        }
    } catch (Exception e) {
        e.printStackTrace();
        return null;
    }
    return result;
}

第二版的解法只用了一层循环，对比第一版解法，从时间花费上看，第二版的解法是优于第一版的。