leetcode: Two Sum

问题描述

    Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

 

原问题链接：https://oj.leetcode.com/problems/two-sum/

 

问题分析

　　这个问题相对来说比较简单，在给定一组数字的时候，我们需要去找两个数字之和为给定数字的一个组合。所以从最开始来说，一个最简单直接的方法就是二重循环遍历数组，找到匹配的就返回。这种方法的实现如下：

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

    这个办法非常的简单直观，不过从性能角度来说却不行。它的时间复杂度达到了O(N^2) 。那么，有没有办法将这个办法改进，以使得它的性能提升呢？

　　这个时候，我们会考虑到另外一个办法，就是原来的方法里是盲目的一个个的去比较和查找。如果有一个办法可以让我们有常量的时间内去查找对应的值是否存在，这样效率就会提升更多。于是，我们可以考虑用map的数据结构。这样我们一次遍历就解决问题了，每次我们遍历的时候就去判断map.containsKey(target - numbers[i])，如果有，则表示前面已经存在一个相加等于target的元素了。没有的话则将该元素加入到map里。按照这个思路，详细的代码实现如下：

 

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] twoIndex = new int[2];    
        for(int i = 0; i < numbers.length; i++) {
            if(map.containsKey(target - numbers[i])) {
                twoIndex[1] = i + 1;
                twoIndex[0] = map.get(target - numbers[i]) + 1;
                return twoIndex;
            }
            map.put(numbers[i], i);
        }
        
        return null;
    }
}

 　　代码的实现比较简单。就不赘述了。里面的一些细节还是值得思考的。

　　在有的时候，我们开始会这么想。既然要查找一个数字是否有对应的target-number[i]的数字存在。那么我们首先把所有的数字都放到一个HashMap里，然后再一个个的去查这样也可以啊。这样会存在的一个问题就是如果我们取到一个值a[i]，而target-a[i]的值正好也等于a[i]的时候，我们没法判断这是不是不同的两个元素的和。而且如果最开始的数组里有重复的元素也会是一个麻烦。