剑指 Offer 42. 连续子数组的最大和

连续子数组问题，解法很经典，就是大于0我就加，否则就不加：
image.png
image.png
与常规dp不太一样的是，这一题看的不是单纯的nums[i]，而是反常的有dp[i-1]
那么问题其实就是看前面的数的和是否是大于0的，大于0的时候，对和有正向增益，小于0的时候没有增益，不如另起一段。
这个思路换个角度也是正确的，就是下面一幅图，就看加上当前值是否更大的，不是的话，从现在开始另起一段。
其实本质上就是选不选的问题，如果选的话，就不是另起炉灶，那么还是满足子数组连续，如果不选，另起炉灶，还是满足了子数组连续，满足了dp定义。

  1. pub fn max_sub_array(nums: Vec<i32>) -> i32 {
  2.     let mut dp = vec![nums[0]; nums.len()];
  3.     let mut res = dp[0];
  4.     for i in 1..nums.len() {
  5.         if dp[i-1] > 0 {
  6.             dp[i] = dp[i-1] + nums[i];
  7.         }else { 
  8.             dp[i] = nums[i];
  9.         }
  10.         res = res.max(dp[i]);
  11.     }
  12.     res
  13. }
  14. // 优化
  15. pub fn max_sub_array(nums: Vec<i32>) -> i32 {
  16.     let mut res = nums[0];
  17.     let mut pre = 0;
  18.     for i in 0..nums.len() {
  19.         pre = nums[i].max(nums[i] + pre);
  20.         res = res.max(pre);
  21.     }
  22.     res
  23. }

剑指 Offer 48. 最长不含重复字符的子字符串

之前面试写的代码，其实是有问题的。

  1. pub fn length_of_longest_substring(s: String) -> i32 {
  2.     use std::collections::HashSet;
  4.     let mut set = HashSet::new();
  5.     let mut res = 0;
  6.     let mut temp = 0;
  7.     s.bytes().for_each(|c| {
  8.         if set.contains(&c) {
  9.             res = temp.max(res);
  10.             set.clear();
  11.             set.insert(c);
  12.             temp = 1;
  13.         } else { 
  14.             set.insert(c);
  15.             temp += 1;
  16.         }
  17.     });
  18.     res
  19. }

实际上的思路是hash+双指针，一次遍历做。
初始化为-1
image.png
当遇到重复的时候，更新最近下标，并移动i到重复的上一次的位置，计算长度
image.png
代码：
注意i需要取max即可

  1. pub fn length_of_longest_substring(s: String) -> i32 {
  2.     use std::collections::{HashMap};
  4.     let mut map = HashMap::new();
  5.     let ss = s.bytes().collect::<Vec<_>>();
  6.     let (mut res, mut i) = (0, -1);
  7.     for j in 0..ss.len() {
  8.         if map.contains_key(&ss[j]) {
  9.             // i修改为重复元素上一次位置，注意！！！！必须加上max，不然
  10.             // 比如abba的情况，在遇到第二个a时会回到i=0，造成算大了
  11.             i = i.max(map[&ss[j]] as i32);             
  12.             let x = map
  13.                 .entry(&ss[j])
  14.                 .or_insert(1);
  15.             *x = j;                            // 修改为最新值
  16.         }else {
  17.             map.insert(&ss[j], j);
  18.         }
  19.         res = res.max(j as i32 - i);
  20.     }
  21.     res
  22. }