01两数之和

题目类型

array；hash-table

思路

1、两层循环。都是从0..nums.len(),如果等于target，就返回。时间复杂度：On^2

// twosum.rs 
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    for i in 0..nums.len()-1 {
        for j in i+1..nums.len() {
            if nums[i] + nums[j] == target {
                return vec![i as i32, j as i32];
            }
        }
    }
    return vec![];
}

Leetcode 结果：

执行用时	内存消耗	语言
52 ms	2.1 MB	Rust

2、Hash-table法。一遍循环，将已经见过的数字及下标存入字典，并对下一个数字判断它与target的差值是否已经在字典里出现过。时间复杂度O(n)

/*
 * @lc app=leetcode.cn id=1 lang=rust
 *
 * [1] 两数之和
 */

// twosum.rs 
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    use std::collections::HashMap;
    let mut seen_nums = HashMap::new(); // seen_nums: 保存已经见过的数字及对应索引

    for (i, val) in nums.iter().enumerate() { // i: 索引，val：数值
        match seen_nums.get( &(target-val) ) {
            Some(seen_num) => {
                return vec![ *seen_nums.get(&(target-val)).unwrap() ,i as i32]; // get 返回Option(&V); i为usize
            }
            None => {
                seen_nums.insert(val, i as i32); // i 是 usize
            }
        }
    }
    vec![]
}


// 测试：lib.rs
mod twosum;

#[cfg(test)]
mod tests {
    use crate::twosum::two_sum;
    #[test]
    fn test_twosum() {
        assert_eq!(vec![1, 2], two_sum(vec![3, 2, 4], 6));
        assert_eq!(vec![0, 1], two_sum(vec![2, 7, 11, 15], 9));
        assert_eq!(vec![0, 2], two_sum(vec![-1, 33, 1, 0], 0 ));
    }
}
 

Leetcode 结果：

执行用时	内存消耗	语言
0 ms	2.7 MB	Rust

Tips

nums.iter().enumerate()对数组进行迭代并显示下标；用 match 替代if

Leetcode 中相似的题型

136题：只有1个数字出现了一次。1. 使用异或^; 2. 使用HashTable; 时间复杂度O(n)

961：重复N次的元素。题目中只有1个数有重复，直接使用HashSet即可。时间复杂度O(n)