Leetcode-01 —— Two Sum

Description

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].

测试用例

根据题意，每个输入都有解，因此数组元素个数一定是大于 2

// 普通测试用例
[3, 4, 2, 1]
6
// 重复元素测试
[1, 1, 2]
2
[1, 1, 1, 1, 1]
2
// 元素只能使用一次测试用例
[4, 1, 3]
4

朴素算法

储备知识

Java 数组定义

int[] arr; // 申明引用变量
int[] arr = new int[10]; // 申明引用并且绑定(分配内存)
int[] arr = {1, 2, 3}; // 申明并且初始化：绑定 + 初始化
new int[]{1, 2, 3};   // 创建数组对象，不与引用变量做地址绑定，一般用于函数的 return 中，如下：

public int[] makeArray(int a, int b) {
    return new int[]{a, b};
}

Solution

两层循环，需要特别注意的是每个元素只能使用一次，因此需要添加判断条件 i != j：

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

        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < nums.length; j++) {
                if(i != j && nums[i] + nums[j] == target) {
                   return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

使用 HashMap

储备知识

Map

顾名思义， Map 是一种映射，就像是数学中的函数映射一样。 $ y = f(x) $ 中，对于作用域内任意的 x 都有为一与之对应的值 y。同理，在 Map 中，任意的 key 和 value 都有一一对应的关系。

Java 中，Map 是一个抽象接口，提供了常用的方法：

功能	方法	备注
判断某个 key 是否存在 map 中	boolean map.containsKey(key)	map.get(key) == null 也可以
向 map 中插入元素	object map.put(key, value)
根据 key 在 map 获取元素	object map.get(key)	如果key不存在，则返回 null
判断 map 是否为空	map.size() == 0 或者 isEmpty()	size() 返回键值对映射数量

泛型

泛型程序设计（generic programming）是程序设计语言的一种风格或范式。泛型允许程序员在强类型程序设计语言中编写代码时使用一些以后才指定的类型，在实例化时作为参数指明这些类型。

——维基百科

意思就是在程序设计时使用一种通用的数据类型，在实例化的时候再指定具体的类型，如下：
1
2
3
public void generic(<T> T) {
// code here ...
}

Solution

根据 HashMap 的特点，我们可以将数组中的每个元素作为 key，数组元素的索引位置作为 value 构建一个 HashMap，然后遍历数组，遍历到第 i 个元素时，如果存在另一个元素与第 i 个元素之和等于 target，则

让 key = target - nums[i] , hashmap.containsKey(key) 返回 true

按照如上想法，代码如下：

class Solution {    
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> container = new HashMap<>();
        
        // initialize container
        for (int i = 0; i < nums.length; i++) {
            container.put(nums[i], i);
        }
        
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            if (container.containsKey(key)) {
                return new int[]{i, container.get(key)};
            }
        }
        
        return null;       
    }
}

然后运行第一个测试用例：

1 2	[2,7,11,15] 9

需要注意的是由于 HashMap 的 key 不允许重复，也就是说相同的 key 会被覆盖掉，试想如下测试用例：

1 2	[2,2,2,2,3,4] 4

这个测试用例返回的结果是 [0, 3] ，这是因为 hashmap 中 key 为 2 的 hash 值被多次修改，最终为 3。

但是一个元素只能使用一次，试想如果 target - nums[i] 的值正好等于 nums[i] 的值会是怎样？

1 2	[2, 1, 3] 4

以上测试用例输出 [0, 0]，而正确答案应该是 [1, 2]。为了去重复，正确的判断条件应该是，

让 key = target - nums[i]，满足： hashmap.containsKey(key) 返回 true 且 hashmap.get(key) != i

改进后的代码如下：

class Solution {    
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> container = new HashMap<>();
        
        // initialize container
        for (int i = 0; i < nums.length; i++) {
            container.put(nums[i], i);
        }
        
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            Integer value = container.get(key);
            if (null != value && value != i) {
                return new int[]{i, value};
            }
        }
        
        return null;      
    }
}

提交后，运行时 2s，打败 98.84%

解释：

Integer value = container.get(key); 这行代码中必须使用 Integer 类型，因为 HashMap 中不存在 key 时 get(key) 返回 null，null 代表空指针引用。
null != value && value != i ，此处 value 是 Integer 类型的 Object，因此与 null 可以进行比较运算，Integer 是基本类型 int 的包装器类型，在与 int 类型的 i 进行比较运算时，自动转换为 int 类型。

参考

大神的骚操作-Solution)