导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一 暴力解法
    2. 方法二 二遍哈希表
    3. 方法三 一遍哈希表

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

翻译

给出一个整形数组,返回其中和为目标数字的两个数字的索引。
你可以认为每个输入都有且只有一个解,并且不可以使用同一个元素两次。
例:
nums = [2, 7, 11, 15],target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
返回 [0, 1]。

方法一 暴力解法

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}

时间复杂度:O(n2)
空间复杂度:O(1)

方法二 二遍哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}

时间复杂度:O(n)
空间复杂度:O(n)

方法三 一遍哈希表

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}

时间复杂度:O(n)
空间复杂度:O(n)