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

思路

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

暴力两次循环

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

impl Solution{  pub fn two_sum(nums: Vec, target: i32) -> Vec {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, target: i32) -> Vec {                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, target: i32) -> Vec {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 问题。

题型与相似题

题型

数组
哈希表

相似题

Two Sum II - Input array is sorted
Two Sum III - Data structure design
3 Sum
3 Sum Smaller
3 Sum Closet
4 Sum

代码

two_sum

参考资料

HashMap文档: HashMap