0001. Two Sum

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

思路

  1. 暴力 时间复杂度 O(n2) 空间复杂度 O(1)
  2. 哈希 时间复杂度 O(n) 空间复杂度 O(n))
  3. 排序再查找 时间复杂度 O(nlogn) 此题返回下标不可行,相似题可行

暴力两次循环

学过其他语言的,很容易写出的代码

impl Solution
{
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {

let len = nums.len();
for i in 0..len {
for j in i+1..len {
if nums[i] + nums[j] == target {
return vec![i as i32, j as i32];
}
}
}

vec![]
}
}

  • 执行用时: 40 ms
  • 内存消耗: 2.1 MB

for循环两次,判断是否相等。
如果要使用数组的迭代器,那第二次循环只能重头开始,需要判断index是否相等。

impl Solution
{
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {

for(i, num_i) in nums.iter().enumerate()
{
for (j, num_j) in nums.iter().enumerate()
{
if i != j && num_i + num_j == target
{
return vec![i as i32, j as i32]
}
}
}
vec![]
}
}

  • 执行用时: 76 ms
  • 内存消耗: 2 MB

HashMap

我们考虑使用HashMap,拿空间换时间。
如果没有在哈希表中就插入,有就返回结果。

use std::collections::HashMap;

impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::with_capacity(nums.len());
for(index,num) in nums.iter().enumerate() {
if let Some(&find) = map.get(&(target-num)) {
return vec![find as i32, index as i32];
}
map.insert(num,index);
}
vec![]
}
}

  • 执行用时: 0 ms
  • 内存消耗: 2.3 MB

需要注意,返回的是索引,所以插入哈希表时key应该是nums中的值,value才是index。

问题与优化思路

问题:
对Rust语法不算熟悉,需要查文档才能知道HashMap的用法。
做算法题,开始得画图来理清自己的思路,确定需求和数据边界,这题中返回下标是首先要确定的需求。

优化思路:
此题如果不返回下标,会有先排序后查找的算法作为X Sum的基础解决算法。
X Sum的解题思路主要是把它转化为(X-1)Sum,最后成为2Sum问题,得到最后的答案。
这其中的转换就是,选出一个元素a,然后就变成target为 -a 的(X-1)Sum 问题。

题型与相似题

题型

  1. 数组
  2. 哈希表

相似题

  1. Two Sum II – Input array is sorted
  2. Two Sum III – Data structure design
  3. 3 Sum
  4. 3 Sum Smaller
  5. 3 Sum Closet
  6. 4 Sum

代码

two_sum

参考资料

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s