LeetCode—1—Two Sum（哈希表的使用）

题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

翻译

给定一个整数数组，找出其中两个数满足相加等于你指定的目标数字。
每个输入只有一个唯一解。相同的元素不能用两次。

解题思路

那么本题呢双重循环的方法在这里就不说了。主要展示一下借助HashMap实现。以及要考虑的问题。
思路还是比较简单的。首先我们把所有元素放到map中。key为元素本身。value为元素在数组中的索引值。放到map中是因为方便查找元素的位置。同时哈希表查找元素的时间复杂度是O（1）级别的。
然后再遍历一边数组。查找map中对应的那个元素。
代码如下

// 1. Two Sum
// https://leetcode.com/problems/two-sum/description/
// 时间复杂度：O(n)
// 空间复杂度：O(n)
public class Solution2 {

    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
        for(int i = 0 ; i < nums.length ; i ++)
            record.put(nums[i], i);

        for(int i = 0 ; i < nums.length; i ++){

            if(record.containsKey(target - nums[i]))
                if(record.get(target - nums[i]) != i){ //不能是同一个的元素相加等于目标值
                    int[] res = {i, record.get(target - nums[i])};
                    return res;
                }

        }

        throw new IllegalStateException("the input has no solution");
    }
}

题到这里就结束了吗？那么有没有想过这么一种可能。这个数组中假如有两个值都为a的元素。那么我们将数组中的元素放到map中时。后面的那个a就将前面那个a覆盖了。a对应的value值为后面那个a的索引。如图：

如果此题的目标值刚好是2a。就是这两个a相加呢？其实这种情况也没有关系。想想当我们第二次遍历数组时。首先肯定遍历到的是数组中的第一个a。此时我们查找map时。找到的另一个值也是a。而map中的这个a刚好使我们数组中的第二个a。因为map中第一个a已被第二个覆盖掉了。所以取当前数组中的a的索引。同时取map中a的索引。就刚好是我们要的答案。
关注我免费下载CSDN

关注公众号哦