Leetcode 第1题 两数之和(easy)

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

方法(一)：暴力解法

最简单的思路是 for 循环 两层 这样 所有可能的组合 。

时间复杂度：$O_{(n^{2})}$

空间复杂度：$$O(1)$$

举个例子 [1,2,3] 就是 循环 $3^2$ 9次。

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut res =vec![];
    for i in  0..nums.len() {
        for j in  0..nums.len() {
            if i == j { continue;}
            if  nums[i] + nums[j] == target{
                res.push(i as i32);
                res.push(j as i32);
                return Vec;
            }
        }
    }
   res
}

Hash表解法

从小学数学的角度 假设已知 矩阵 b= [ 1,2,7 ] 矩阵c = [9,9,9] 定义 a + b = c ,那么按照矩阵的加法运算.

a = c - b = [9,9,9] -[1,2,7] = [8,7,2] ，按照题目的定义 我们要求一个数 即满足 a + b = c, 同时 这个数 既属于矩阵a的子集 又属于 矩阵b的子集 ,那么 就可以表示为 $b{\bigcap}a $ 那么把[1,2,7] $\bigcap$ [8,7,2] 那么 答案就是 7 和 2 但是 题目说一个元素不能被使用2次,那么如果是取 b = 2 那么 a = 7 如果 取 b = 7 那么 a = 2 按照for 循环顺序,2 在前 所以 会去到 b =2 , a = 7。

综上分析：我们在每次循环 都把当前数的 另一半使得 a + b = c 的数算出来, 然后存起来,下次循环到下一个数的时候，去找下有没有记录,有的话就就直接返回结果。

那用什么存呢? 想想计算机的数据结构无非就那么几种,数组,栈,链表、HashMap 啊

• 如果用数组,那么每次循环前就判断下,当前这个数是否在数组里被记录过了 可以用contains。,时间复杂度O(n!)、另外链表的复杂度也是一样的,用数组、链表 其实也就变成了暴力解法。

• 红黑树,时间复杂度(O(n$log_n$)) 红黑树相对快点,但还不是最高效的。

• Hash表,hash表可以直接O(1)的复杂度,可以把 a 或者 b 当做key value 随便放什么值, 只要能在表里找到的就是能解的。

综上总结:使用 Hash 表的 复杂度为O(1),我们把 ,如果我们 给定 a = 1,c =8 那么 我们 只要在 hash 表的key里存 b = c - a = 7 那么 下次数组遍历到 7 然后去hash 表get(7) 有值,就说明 配对成功了 ，我们可以把hash表看作一个交友网站,你把你想要找的另一半 要求给记下了给到它,下次人家只要从这个等级的记录里面配对就好了。

use std::collections::HashMap;
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut map: HashMap<i32, i32> = HashMap::new();
        for (i, v) in nums.iter().enumerate() {
            match map.get(v) {
               //匹配到 直接返回
                Some(&index) => { return vec![index, i as i32] }
              //匹配不到 把当前数对应的解b = c -a  插入 value
                _ => { map.insert(target-v, i as i32); }
            }
        }
        vec![]
    }
}

就暴力算法,在对比了 其他几门语言 发现性能还是比较出类拔萃的,基于同样逻辑用C实现的暴力算法 执行速度上 也比Rust满很多 不知道为什么 python 更是没法比相差 100多倍的,Go也是比较出色的能和,保Rust持同一个水平。