目录
3. 无重复字符的最长子串 Longest substring without repeating characters 🌟🌟
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^4s由英文字母、数字、符号和空格组成
代码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
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/