2022-09-17：一个字符串 s，表示仓库的墙与货物，其中‘|‘表示墙,‘*‘表示货物。给定一个起始下标 start 和一个终止下标 end，找出子串中被墙包裹的货物数量。比如： s = “

2022 年 9 月 17 日
北京
本文字数：1114 字
阅读完需：约 4 分钟

2022-09-17：一个字符串 s，表示仓库的墙与货物，其中'|'表示墙,''表示货物。给定一个起始下标 start 和一个终止下标 end，找出子串中被墙包裹的货物数量。比如：s = "|||"，start = 1, end = 7，start 和 end 截出的子串是 "||"，被 '|'包裹的 '' 有两个，所以返回 2，现在给定一系列的 start，startIndices[]，和对应一系列的 end ,endIndices[]。返回每一对[start,end]的截出来的货物数量。数据规模：字符串 s 长度<=10^5，startIndices 长度 == endIndices 长度 <=10^5。亚马逊的货物和墙的问题。

答案 2022-09-17：

前缀和。时间复杂度：O(N)。空间复杂度：O(N)。

代码用 rust 编写。代码如下：

fn main() {    let s = "|**|**|*";    let mut a = vec![0, 1, 3, 4];    let mut b = vec![7, 7, 6, 5];    let ans = number(s, &mut a, &mut b);    println!("ans = {:?}", ans);}
fn number(s: &str, starts: &mut Vec<i32>, ends: &mut Vec<i32>) -> Vec<i32> {    let str = s.as_bytes();    let n = str.len() as i32;    let mut left: Vec<i32> = vec![];    let mut right: Vec<i32> = vec![];    let mut sum: Vec<i32> = vec![];    for _ in 0..n {        left.push(0);        right.push(0);        sum.push(0);    }
    let mut pre = -1;    let mut num = 0;    for i in 0..n {        pre = if str[i as usize] == '|' as u8 { i } else { pre };        num += if str[i as usize] == '*' as u8 { 1 } else { 0 };        left[i as usize] = pre;        sum[i as usize] = num;    }    pre = -1;    let mut i = n - 1;    while i >= 0 {        pre = if str[i as usize] == '|' as u8 { i } else { pre };        right[i as usize] = pre;        i -= 1;    }
    let m = starts.len() as i32;    let mut ans: Vec<i32> = vec![];    for _ in 0..m {        ans.push(0);    }    for i in 0..m {        ans[i as usize] = stars(            starts[i as usize],            ends[i as usize],            &mut left,            &mut right,            &mut sum,        );    }    return ans;}
fn stars(start: i32, end: i32, l: &mut Vec<i32>, r: &mut Vec<i32>, s: &mut Vec<i32>) -> i32 {    let left = r[start as usize];    let right = l[end as usize];    if left == -1 || right == -1 || (left >= right) {        return 0;    }    return if left == 0 {        s[right as usize]    } else {        s[right as usize] - s[(left - 1) as usize]    };}