Two Sum

发表于 | 分类于 | 阅读次数:
字数统计: 684 | 阅读时长 ≈ 3

问题描述

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

这一题大致是说在给定的整数数组中找到两个整数，使得两个数字的和等于一个给定的数，这里假定问题存在一个解。

解法

暴力求解的时间复杂度过高，当然还有采用先排序再两边夹逼的方法，但是目前比较好的方法是采用Hash表。

Hash表解此题的核心思想是用key存储原数组中的值，用value存储原数组值的索引。

此题假设每种输入只会对应一个答案，但是并非不能有重复的数出现，比如提供的数组为[5,3,3,5,7]，如果target是6，那么下面的哈希(1)方法并不能处理这种情况。

哈希(1)

事先存好，存好后如果出现相同的数会覆盖前面出现的数，这里不妨采用HashMap。下面手写实现的类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
    pubic int[] twoSum(int[] numbers,int target )
    {
      int[] res = new int[2];
      Map map = new HashMap();
      for(int i = 0; i < numbers.length; i++ )
      {
        map.put(numbers[i],i);
      }
      for(int i = 0;i < numbers.length; i++)
      {
        int gap = target - numbers[i];
        if (map.get(gap) != null && (int)map.get(gap) != i)
        {
        res[0] = i+1;
        res[1] = (int)map.get(gap) + 1;
        break;
        }
      }
      return res;
    }
}

在这段代码中，首先将提供的数组全部存储在容器中，这里如果存在相同的数，会覆盖。由于题目假设只有一个解，那么重复的数字不会超过2。if语句中!= i，是因为自己总是会和自己相等。

编写测试用例：

1
2
3
4
5
6
7
8
9
10
11
import java.io.*;
import java.util.*;
public class Test
{
  public static void main(String[] args)
  {
    Solution a = Solution();
    int[] number1 = new int[]{5,3,3,5,7};
    System.out.println(Arrays.toString(a.twoSum(number1,6)));
  }
}

输出[2,3]。

哈希(2)

判断当前数组的元素是不是已经存在在Hash容器中，没有的时候，就把当前的添加进去。前面介绍的第一种Hash方法是后面的把前面覆盖，这一种是前面出现了后面就不添加了，同样能解决重复问题,这里我另用hashtable。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
  public int[] twoSum(int[] numbers,int target)
  {
    int[] res = new int[2];
    Hashtable<Integer,Integer> ta = new Hashtable<Integer,Integer>();
    for(int i = 0;i < numbers.length;i++)
    {
      if(ta.get(target-numbers[i]) != null && ta.get(target-numbers[i]) < i)
      {
        res[0] = ta.get(target-numbers[i]) + 1;
        res[1] = i + 1;
        break;
      }
      if(ta.get(numbers[i]) == null)
      ta.put(numbers[i],i);
    }
    return res;
  }
}

小结

以上算法的时间复杂度是O(n)。