LeetCode 1. Two Sum [Easy]

发表于 更新于 分类于 ， 阅读次数：

题目来源：https://leetcode.com/problems/two-sum/

题目难度：Easy

题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

解答1[Java]：暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

注意内层的 for 循环，其中的初始条件是 int j = i + 1。根据本题的条件，因为一个数最多只能匹配上一次，所以 i 前边的数据都已经遍历过了，所以可以跳过。

复杂度分析

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

解答1[Java]：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.HashMap;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            // 边遍历边判断，而不是先构建哈希表再判断，这种效率更高
            if (map.get(target - nums[i]) != null) {
                return new int[] { map.get(target - nums[i]), i };
            } else {
                map.put(nums[i], i);
            }
        }

        throw new IllegalArgumentException("No two sum solution");
    }
}

因为题目中说了本体有且只有一个答案，那么说明数组中的满足条件的元素一定是不重复的，不然无法保证答案唯一。既然满足条件的元素是唯一的，那么就可以使用哈希表来解决了。哈希表的键为元素的值，哈希表的值为元素的索引。

扩展：即使满足条件的元素不唯一，还是可以使用哈希表，哈希表中的值使用一个列表，保存多个索引即可。

复杂度分析

时间复杂度：$O(n)$，最坏情况下，要把整个数组遍历一遍。

空间复杂度：$O(n)$