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

思路

• 暴力 O(N2)

• Hash O(N）

暴力两次循环 学过其他语言的，很容易写出的代码

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![] }}

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![]    }}

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() { match map.get(&(target-num)) { None => {map.insert(num,index);} Some(find) => {return vec![*find as i32, index as i32]} } } vec![] }}

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

####

#### 参考

- HashMap文档

           https://doc.rust-lang.org/std/collections/struct.HashMap.html