Skip to main content

Two Sum

两个解法

  • 排序后从两端逼近 Onlogn & Ologn
  • 一遍扫描,用哈希表存储已扫数 On & On
快排解法
struct Num{    i: usize,    v: i32}
impl Solution {    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {        use std::convert::TryInto;
        let mut nums  = nums.iter().enumerate().map(|(i, v)| {            Num{i: i.clone(), v: v.clone()}        }).collect::<Vec<_>>();
        nums.sort_by(|a, b| {            a.v.cmp(&b.v)        });        let mut l = 0;        let mut r = nums.len() - 1;
        while l < r {            let res = nums[l].v + nums[r].v - target;            if res == 0 {                return vec![nums[l].i.try_into().unwrap(), nums[r].i.try_into().unwrap()];            } else if res > 0 {                r = r - 1;            } else if res < 0 {                l = l + 1;            }        }        unreachable!();    }}