2022-05-18：假设数组a和数组b为两组信号： 1) length(b) ＜= length(a)； 2) 对于任意0＜=i＜length(b), 有b[i+1] - b[i] == a[i+1

2022-05-18：假设数组a和数组b为两组信号：

length(b) <= length(a)；
对于任意0<=i<length(b), 有b[i+1] - b[i] == a[i+1] - a[i]。
那么就称信号b和信号a一致，记为b==a，
给你好多b数组，假设有m个: b0数组、b1数组…
给你好多a数组，假设有n个: a0数组、a1数组…
返回一个长度为m的结果数组ans，ans[i]表示 : bi数组和多少个a数组一致。
来自字节飞书团队。

答案2022-05-18：

前缀树。

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

use std::collections::HashMap;

use std::sync::Arc;

use std::sync::Mutex;

fn main() {

    let mut bs: Vec<Vec<isize>> = vec![vec![1, 7, 5], vec![2, 8, 6, 24]];

    let mut as0: Vec<Vec<isize>> = vec![vec![1, 7, 5], vec![2, 8, 6, 24]];

    let ans = same_teams_array(&mut bs, &mut as0);

    println!("ans = {:?}", ans);

}

fn same_teams_array(bs: &mut Vec<Vec<isize>>, as0: &mut Vec<Vec<isize>>) -> Vec<isize> {

    let m = bs.len() as isize;

    let mut root = Arc::new(Mutex::new(TrieNode::new()));

    let mut cur = Arc::clone(&mut root);

    let mut cur2 = Arc::clone(&mut cur);

    for i in 0..m {

        let k = bs[i as usize].len() as isize;

        cur = Arc::clone(&mut root);

        for j in 1..k {

            let diff = bs[i as usize][j as usize] - bs[i as usize][(j - 1) as usize];

            if !cur.lock().unwrap().nexts.contains_key(&diff) {

                cur.lock()

                    .unwrap()

                    .nexts

                    .insert(diff, Arc::new(Mutex::new(TrieNode::new())));

            }

            let c2 = Arc::clone(&mut cur.lock().unwrap().nexts.get(&diff).unwrap());

            cur = c2;

        }

        cur.lock().unwrap().indices.push(i);

    }

    let mut ans: Vec<isize> = vec![];

    for _i in 0..m {

        ans.push(0);

    }

    let n = as0.len() as isize;

    for i in 0..n {

        let k = as0[i as usize].len() as isize;

        cur = Arc::clone(&mut root);

        for j in 1..k {

            let diff = as0[i as usize][j as usize] - as0[i as usize][(j - 1) as usize];

            if !cur.lock().unwrap().nexts.contains_key(&diff) {

                break;

            }

            let c2 = Arc::clone(&mut cur.lock().unwrap().nexts.get(&diff).unwrap());

            cur = c2;

            for index in &cur.lock().unwrap().indices {

                ans[(*index) as usize] += 1;

            }

        }

    }

    return ans;

}

pub struct TrieNode {

    pub indices: Vec<isize>,

    pub nexts: HashMap<isize, Arc<Mutex<TrieNode>>>,

}

impl TrieNode {

    pub fn new() -> Self {

        Self {

            indices: vec![],

            nexts: HashMap::new(),

        }

    }

}

执行结果如下：

---

左神java代码

2022-05-18：假设数组a和数组b为两组信号： 1) length(b) ＜= length(a)； 2) 对于任意0＜=i＜length(b), 有b[i+1] - b[i] == a[i+1的相关教程结束。