给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题型归类: vec, 循环, HashMap
使用循环，拿第一个数，然后开始分别与第二个数，第三个数相加...第n个相加，如果和等于target，那么就返回结果。如果不等，那么开始第二次循环，第二个数，分别与第三，第四个数...第n个相加，依次类推。
// 代码实现
impl Solution {
pub fn two_sum3(mut nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut index = 0; // 记录最外层循环的index
let length = nums.len() as i32;
// 使用nums.pop()，这样nums就缩短了，查找的时候就少了一次循环
while let Some(i) = nums.pop() {
for (index2, i2) in nums.iter().enumerate() {
if (i+*i2) == target {
// length - index -1 获得第二个循环中渠道的数字 在原始nums中的index
return vec![index2 as i32, length-index-1];
}
}
index += 1;
}
vec![0]
}
}
#[cfg(test)]
mod tests {
use crate::Solution;
#[test]
pub fn add_two_numbers_test() {
assert_eq!(vec![1, 2], Solution::two_sum(vec![5, 7, 2], 9));
assert_eq!(vec![0, 2], Solution::two_sum(vec![5, 7, 5, 2], 10));
assert_eq!(vec![2, 3], Solution::two_sum(vec![1, 2, 3, 4], 7));
}
}
执行用时 : 28 ms , 在所有 Rust 提交中击败了 44.75% 的用户
内存消耗 : 2 MB , 在所有 Rust 提交中击败了 100.00% 的用户
这么做思路简单清晰，内存消耗低，但是不好就是会进行很多次循环，如果数组很长，那么就会随着数组长度变长，时间消耗就会成倍增加，效率不是那么高。这个算法中，需要进行的循环次数为n的阶乘次，即 $ n!=n * (n-1) , n! = n^2 - n $ 即，算法复杂度为$O(n^2)$， 因此需要想一个新的思路，只用一次循环，把算法复杂度变为$O(n)$。
只用一次循环，用target与每次的数字相减得到结果A，然后查找剩余数字里面有没有A这个数字, 引入HashMap来查找有没有相减结果A，没有找到的时候，就把数字放入HashMap然后继续找，如果找到了就返回结果。
// 代码实现
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut data = HashMap::new();
for (index, n) in nums.iter().enumerate() {
match data.get(&(target - *n)) {
None => data.insert(n, index),
Some(index2) => return vec![*index2 as i32, index as i32]
};
}
vec![]
}
}
#[cfg(test)]
mod tests {
use crate::Solution;
#[test]
pub fn add_two_numbers_test() {
assert_eq!(vec![1, 2], Solution::two_sum(vec![5, 7, 2], 9));
assert_eq!(vec![0, 2], Solution::two_sum(vec![5, 7, 5, 2], 10));
assert_eq!(vec![2, 3], Solution::two_sum(vec![1, 2, 3, 4], 7));
}
}
执行用时 : 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2.7 MB , 在所有 Rust 提交中击败了 61.14% 的用户
这个思路，只使用一次循环，执行用时缩短为约等于0ms，循环次数为n, 算法复杂度为$O(n)$, 由于引入了HashMap，内存稍微增加了一点。这是划算的，越短的执行时间，就可以支撑越多的用户并发。
2019-09-02 06:02