0%

LeetCode 1. Two Sum -- 两数之和

Description

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.

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回它们的数组下标

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现

你可以按任意顺序返回答案

Example 1:

1
2
3
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]

Example 3:

1
2
Input: nums = [3, 3], target = 6
Output: [0, 1]

Constraints:

  • 2 <= nums.length <= 103
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists

Solution

Approach 1: Brute Force

思路

  • 暴力枚举是最容易想到的方法。通过循环遍历数组中的数字 x,寻找数组中是否存在 target - x
  • 需要注意的有两个点:1. 寻找 target - x 时,每一个位于 x 之前的元素都已经和 x 匹配过,所以就不需要重复匹配了;2. 每一个元素不能被使用两次,所以也是只需要在 x 后面的元素中寻找 target - x 即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
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.[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
return new int[0];
}
}

复杂度分析

  • 时间复杂度:O(N2)。N 是数组中元素的数量,最坏情况下数组中任意两个数字都要被匹配一次
  • 空间复杂度:O(1)。显而易见,暴力枚举不需要额外存储空间

Approach 2: Two-pass Hash Map

思路

  • 大多数算法题往往都不只有一种方法,优化的解法基本是从降低时间复杂度的角度出发的(对空间复杂度的优化并不是重点)。所以,针对本道题目暴力枚举的时间复杂度是 O(N2),从算法的角度来看并不是很理想的一个量级,所以我们还需要寻找是否有更理想时间复杂度的算法

  • 对于这道算法题,关键的优化点就是更高效地寻找 complement,即 target - nums[i]。我们期望更高效地寻找到 complement,然后输出对应的 index,所以比较容易想到这种键和值的映射常用的数据结构就是哈希表。具体的思路就是使用一个哈希表再加上两次迭代,第一次迭代我们把数组元素的值和对应的索引分别作为键和值保存到哈希表中。在第二次迭代中再去遍历这个哈希表看是否存在 complement。需要注意的是,根据题目要求,complement 不能匹配 nums[i] 本身

代码

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

复杂度分析

  • 时间复杂度:O(n)。哈希表的查找和插入操作都是 O(1),而且虽然是两次循环迭代,但这两次迭代是先后顺序并不是嵌套关系
  • 空间复杂度:O(n)。需要借助一个哈希表

Approach 3: One-pass Hash Map

思路

  • 基于解法 2 其实还有一种优化方法,这种方法并不是从降低复杂度的角度出发而是从优化代码实现逻辑的角度出发
  • 解法 2 是用了两次迭代,即先保存再查找,实际上只用一次迭代也是可以完成保存和查找操作,实现巧妙。也就是说在一次迭代的过程中一边进行查找一边进行插入,因为是先查找再插入,也就能避免和该元素本身的匹配,从而满足题目要求

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashMap = new HashMap<> ();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (hashMap.containsKey(complement)) {
return new int[] {map.get(complement), i};
}
hashMap.put(nums[i], i);
}
return new int[0];
}
}

复杂度分析

  • 时间复杂度:O(n)。一个哈希表,一次迭代
  • 空间复杂度:O(n)。需要借助一个哈希表
-------------------- 本文结束感谢您的阅读 --------------------