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

参考资料

• HashMap文档: HashMap