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