leetcode 1-20题

Leetcode 1-20

1.两数之和

1. 两数之和 - 力扣（LeetCode）

找出数组中两个和为 target 的数的索引。

【初始想法】使用两重 for 循环, 时间复杂度 o(n^2 / 2)

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

由于要求：时间复杂度小于 o(n^2) 级别，那么就想 o(nlogn) 或者 o(n) 的算法。

因为要求的是两个变量，操作两个变量总是需要两重循环才能完成，如果可以将一重循环的时间复杂度降到 o(logn) 或者 o(1) 那么就可以解决问题。 而在查找技术中：

1. 使用二分查找的是时间复杂度是 o(logn) ,二分需要先排序
2. 使用哈希表查找的时间复杂度是 o(1) , 哈希表需要预处理

【o(nlogn)】 先排序，后二分。但是题目要求的返回对应的索引，那么这样做的话还需要将数组中每个数的索引都存一遍。

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Pair<T, U> {
  x: T,
  y: U,
}
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
  let mut ans: Vec<i32> = vec![];

  //  foo 记录每个数的原索引和 target - nums[index]
  let mut foo: Vec<Pair<i32, i32>> = Vec::new();
  for (index, val) in nums.iter().enumerate() {
    foo.push(Pair {
      x: index as i32,
      y: target - *val,
    });
  }

  //  升序排列
  foo.sort_by(|a, b| a.y.cmp(&b.y));

  // 固定一个数，然后二分搜索另一个数
  for i in foo.iter() {
    let first = i.y;
    let second_index = foo.binary_search_by_key(&(target - first), |pair| pair.y);
    match second_index {
      Ok(index) => {
        if i.x != foo[index].x {
          ans.push(i.x);
          ans.push(foo[index].x);
          break;
        }
      }
      Err(e) => {
        continue;
      }
    }
  }
  ans.sort();
  ans
}

【o(n)】预处理哈希表，将 target - num[i] 和 index 存入哈希表，然后遍历 nums 直接查表即可。

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
  let mut ans = vec![];
  //  mp:{ k: nums[index] , v:index})
  let mut mp: HashMap<i32, u32> = HashMap::new();

  // 预处理哈希表
  nums.iter().enumerate().for_each(|(index, v)| {
    mp.insert(*v, index as u32);
  });

  // 查表
  for (index, v) in nums.iter().enumerate() {
    let addend1 = target - *v;
    let addend2_index = mp.get(&addend1);
    match addend2_index {
      Some(i) => {
        if *i != index as u32 {
          ans.push(index as i32);
          ans.push(*i as i32);
          break;
        }
      }
      _ => {()}
    }
  }
  ans
}

注意

不管是二分还是查哈希表，查的都是全范围。那么就有如下问题： 如果数组中有一个数为 3, target = 6, 由于我遍历方式的原因， 那么就有可能查到多次 3，解决这个问题只需判断一下两个索引是否相同即可。

2.两数相加

2. 两数相加 - 力扣（LeetCode）

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {      // 单链表节点
  pub val: i32,
  pub next: Option<Box<ListNode>>,
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode { next: None, val }
  }
}

pub fn add_two_numbers( l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>,) -> Option<Box<ListNode>> {
  rec(l1, l2, 0)
}

pub fn rec(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>, mut carry: i32) -> Option<Box<ListNode>> {

  // 当两个节点有一个为空且给这个两个节点的进位为空时，加法结束
  if l1.is_none() && l2.is_none() && carry == 0 { None }
  else {
    Some(Box::new(ListNode{
      next: rec(
        l1.and_then(|x| { carry += x.val ; x.next}),
        l2.and_then(|x| { carry += x.val ; x.next }),
        carry / 10    // 进位
      ),
      val: carry % 10   // 进位后的余位       
    }))
  }
}

3.无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

/// i        i       i       i       i
/// abccd   abccd  abccd  abccd  abccd
/// j       j        j       j      j 
/// 维护 [i, j] 区间中每个字符的出现的次数 
pub fn length_of_longest_substring(s: String) -> i32 {
  let mut ans = 0;
  let n = s.len();
  // <char, u32> 记录每个字符在 [i, j] 区间中出现的次数
  let mut mp = HashMap::<char, u32>::new();

  // 将 String 转为 Vec<char>
  let vc: Vec<char> = s.chars().collect();

  // 双指针扫描区间
  let mut j = 0;
  for i in 0..n {
    match mp.get_mut(&vc[i]) {
      Some(x) => *x += 1,
      None => {
        mp.insert(vc[i], 1); ()
      }
    }
    while mp.get(&vc[i]).unwrap() > &1 {
      mp.get_mut(&vc[j]).and_then(|x| Some(*x -= 1));
      j += 1;
    }
    ans = std::cmp::max(ans, (i - j + 1) as i32);
  }
  ans
}