1. 两数之和 Two Sum
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n^2) 的算法吗？
代码1： 暴力枚举
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { let n = nums.len(); for i in 0..n { for j in i+1..n { if nums[i] + nums[j] == target { return vec![i as i32, j as i32]; } } } vec![] } fn main() { let nums = [2, 7, 11, 15]; let target = 9; println!("{:?}", two_sum((&nums).to_vec(), target)); let nums = [3, 2, 4]; let target = 6; println!("{:?}", two_sum((&nums).to_vec(), target)); let nums = [3, 3]; println!("{:?}", two_sum((&nums).to_vec(), target)); }
代码2： 二分查找
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { let n = nums.len(); for i in 0..n { let complement = target - nums[i]; if let Ok(j) = nums.binary_search(&complement) { if i != j { return vec![i as i32, j as i32]; } } } vec![] } fn main() { let nums = [2, 7, 11, 15]; let target = 9; println!("{:?}", two_sum((&nums).to_vec(), target)); let nums = [3, 2, 4]; let target = 6; println!("{:?}", two_sum((&nums).to_vec(), target)); let nums = [3, 3]; println!("{:?}", two_sum((&nums).to_vec(), target)); }
代码3： 哈希表
use std::collections::HashMap; fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { let mut map = HashMap::new(); for (i, num) in nums.iter().enumerate() { let complement = target - num; if let Some(j) = map.get(&complement) { return vec![*j as i32, i as i32]; } map.insert(num, i); } vec![] } fn main() { let nums = [2, 7, 11, 15]; let target = 9; println!("{:?}", two_sum((&nums).to_vec(), target)); let nums = [3, 2, 4]; let target = 6; println!("{:?}", two_sum((&nums).to_vec(), target)); let nums = [3, 3]; println!("{:?}", two_sum((&nums).to_vec(), target)); }
数组 + 哈希表
fn two_sum(nums: &[i32], target: i32) -> Vec<i32> { let mut imap = std::collections::HashMap::new(); for (i, num) in nums.iter().enumerate() { let two = target - num; if let Some(&j) = imap.get(&two) { return vec![j as i32, i as i32]; } imap.insert(num, i); } vec![] } fn main() { let nums = [2, 7, 11, 15]; let target = 9; println!("{:?}", two_sum(&nums, target)); let nums = [3, 2, 4]; let target = 6; println!("{:?}", two_sum(&nums, target)); let nums = [3, 3]; println!("{:?}", two_sum(&nums, target)); }
代码4： 排序+双指针
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { let mut nums = nums; let n = nums.len(); for i in 0..n { nums[i] = nums[i].clone() as i32; } let mut pairs: Vec<(i32, usize)> = nums.iter() .enumerate() .map(|(i, &x)| (x, i)) .collect(); pairs.sort_unstable(); let (mut i, mut j) = (0, n - 1); while i < j { let sum = pairs[i].0 + pairs[j].0; if sum == target { let (index1, index2) = (pairs[i].1 as i32, pairs[j].1 as i32); return vec![index1, index2]; } else if sum < target { i += 1; } else { j -= 1; } } vec![] } fn main() { let nums = [2, 7, 11, 15]; let target = 9; println!("{:?}", two_sum((&nums).to_vec(), target)); let nums = [3, 2, 4]; let target = 6; println!("{:?}", two_sum((&nums).to_vec(), target)); let nums = [3, 3]; println!("{:?}", two_sum((&nums).to_vec(), target)); }
输出：
[0, 1]
[1, 2]
[0, 1]
2. 两数相加 Add Two Numbers
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
代码1： 模拟竖式加法
use std::fmt; struct ListNode { data: i32, next: Option<Box<ListNode>>, } impl ListNode { fn new(data: i32) -> Self { ListNode { data, next: None } } fn build(list: &[i32]) -> Option<Box<ListNode>> { let mut head = None; for i in (0..list.len()).rev() { head = Some(Box::new(ListNode { data: list[i], next: head, })); } head } } impl fmt::Debug for ListNode { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { let mut p = Some(self); while let Some(node) = p { write!(f, "{}->", node.data)?; p = node.next.as_ref().map(|x| x.as_ref()); } write!(f, "<nil>") } } fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> { let mut dummy_head = ListNode::new(0); let (mut p1, mut p2, mut curr) = (l1, l2, &mut dummy_head); let mut carry = 0; while p1.is_some() || p2.is_some() || carry != 0 { let mut sum = carry; if let Some(node) = p1 { sum += node.data; p1 = node.next; } if let Some(node) = p2 { sum += node.data; p2 = node.next; } carry = sum / 10; curr.next = Some(Box::new(ListNode::new(sum % 10))); curr = curr.next.as_mut().unwrap(); } dummy_head.next } fn main() { let l1 = ListNode::build(&[2, 4, 3]); let l2 = ListNode::build(&[5, 6, 4]); println!("{:?}", l1); println!("{:?}", l2); println!("{:?}", add_two_numbers(l1, l2)); let l1 = ListNode::build(&[9,9,9,9,9,9,9]); let l2 = ListNode::build(&[9,9,9,9]); println!("{:?}", l1); println!("{:?}", l2); println!("{:?}", add_two_numbers(l1, l2)); }
代码2： 模拟竖式加法2
use std::fmt; struct ListNode { data: i32, next: Option<Box<ListNode>>, } impl ListNode { fn new(data: i32) -> Self { ListNode { data, next: None } } fn build(list: &[i32]) -> Option<Box<ListNode>> { let mut head = None; for i in (0..list.len()).rev() { head = Some(Box::new(ListNode { data: list[i], next: head, })); } head } } impl fmt::Debug for ListNode { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { let mut p = Some(self); while let Some(node) = p { write!(f, "{}->", node.data)?; p = node.next.as_ref().map(|x| x.as_ref()); } write!(f, "<nil>") } } fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> { let mut dummy_head = ListNode::new(0); let mut p = &mut dummy_head; let mut p1 = l1.as_ref(); let mut p2 = l2.as_ref(); let mut carry = 0; while p1.is_some() || p2.is_some() { let mut sum = carry; if let Some(node) = p1 { sum += node.data; p1 = node.next.as_ref(); } if let Some(node) = p2 { sum += node.data; p2 = node.next.as_ref(); } carry = sum / 10; p.next = Some(Box::new(ListNode::new(sum % 10))); p = p.next.as_mut().unwrap(); } if carry > 0 { p.next = Some(Box::new(ListNode::new(carry))); } dummy_head.next } fn main() { let l1 = ListNode::build(&[2, 4, 3]); let l2 = ListNode::build(&[5, 6, 4]); println!("{:?}", l1); println!("{:?}", l2); println!("{:?}", add_two_numbers(l1, l2)); let l1 = ListNode::build(&[9,9,9,9,9,9,9]); let l2 = ListNode::build(&[9,9,9,9]); println!("{:?}", l1); println!("{:?}", l2); println!("{:?}", add_two_numbers(l1, l2)); }
代码3： 递归法
use std::fmt; struct ListNode { data: i32, next: Option<Box<ListNode>>, } impl ListNode { fn new(data: i32) -> Self { ListNode { data, next: None } } fn build(list: &[i32]) -> Option<Box<ListNode>> { let mut head = None; for i in (0..list.len()).rev() { head = Some(Box::new(ListNode { data: list[i], next: head, })); } head } } impl fmt::Debug for ListNode { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { let mut p = Some(self); while let Some(node) = p { write!(f, "{}->", node.data)?; p = node.next.as_ref().map(|x| x.as_ref()); } write!(f, "<nil>") } } fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> { add_helper(l1.as_ref(), l2.as_ref(), 0) } fn add_helper(l1: Option<&Box<ListNode>>, l2: Option<&Box<ListNode>>, carry: i32) -> Option<Box<ListNode>> { if l1.is_none() && l2.is_none() && carry == 0 { return None; } let mut sum = carry; if let Some(node) = l1 { sum += node.data; } if let Some(node) = l2 { sum += node.data; } let mut node = ListNode::new(sum % 10); node.next = add_helper(l1.map(|x| x.next.as_ref()).flatten(), l2.map(|x| x.next.as_ref()).flatten(), sum / 10); Some(Box::new(node)) } fn main() { let l1 = ListNode::build(&[2, 4, 3]); let l2 = ListNode::build(&[5, 6, 4]); println!("{:?}", l1); println!("{:?}", l2); println!("{:?}", add_two_numbers(l1, l2)); let l1 = ListNode::build(&[9,9,9,9,9,9,9]); let l2 = ListNode::build(&[9,9,9,9]); println!("{:?}", l1); println!("{:?}", l2); println!("{:?}", add_two_numbers(l1, l2)); }
输出：
2->4->3-><nil>
5->6->4-><nil>
7->0->8-><nil>
9->9->9->9->9->9->9-><nil>
9->9->9->9-><nil>
8->9->9->9->0->0->0->1-><nil>
3. 无重复字符的最长子串 Longest substring without repeating characters
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成
代码1： 滑动窗口
use std::collections::HashSet; fn length_of_longest_substring(s: String) -> i32 { let s = s.as_bytes(); let mut set = HashSet::new(); let mut left = 0; let mut right = 0; let mut max_len = 0; while right < s.len() { if !set.contains(&s[right]) { set.insert(s[right]); right += 1; max_len = max_len.max(right - left); } else { set.remove(&s[left]); left += 1; } } max_len as i32 } fn main() { let str = String::from("abcabcbb"); println!("{}", length_of_longest_substring(str)); let str = "bbbbb".to_string(); println!("{}", length_of_longest_substring(str)); let str = "pwwkew".to_string(); println!("{}", length_of_longest_substring(str)); }
代码2： 动态规划
fn length_of_longest_substring(s: String) -> i32 { let s = s.as_bytes(); let mut dp = vec![0; s.len()]; let mut max_len = 0; for i in 0..s.len() { if i == 0 || !s[0..i].contains(&s[i]) { dp[i] = if i == 0 { 1 } else { dp[i-1] + 1 }; } else { let last_pos = s[0..i].iter().rposition(|&x| x == s[i]).unwrap(); dp[i] = i - 1 - last_pos + 1; } max_len = max_len.max(dp[i]); } max_len as i32 } fn main() { let str = String::from("abcabcbb"); println!("{}", length_of_longest_substring(str)); let str = "bbbbb".to_string(); println!("{}", length_of_longest_substring(str)); let str = "pwwkew".to_string(); println!("{}", length_of_longest_substring(str)); }
代码3： 双指针
fn length_of_longest_substring(s: String) -> i32 { let s = s.as_bytes(); let mut last_pos = vec![-1; 256]; let mut left = 0; let mut right = 0; let mut max_len = 0; while right < s.len() { if last_pos[s[right] as usize] < left as i32 { last_pos[s[right] as usize] = right as i32; right += 1; max_len = max_len.max(right - left); } else { left += 1; } } max_len as i32 } fn main() { let str = String::from("abcabcbb"); println!("{}", length_of_longest_substring(str)); let str = "bbbbb".to_string(); println!("{}", length_of_longest_substring(str)); let str = "pwwkew".to_string(); println!("{}", length_of_longest_substring(str)); }
输出：
3
1
3
