2023-09-01：用go語(yǔ)言編寫(xiě)。給出兩個(gè)長(zhǎng)度均為n的數(shù)組，

A = { a1, a2, ... ,an }，

B = { b1, b2, ... ,bn }。

你需要求出其有多少個(gè)區(qū)間[L,R]滿足:

數(shù)組A中下標(biāo)在[L,R]中的元素之和在[La,Ra]之中，

數(shù)組B中下標(biāo)在[L,R]中的元素之和在[Lb,Rb]之中。

輸入：

第一行有一個(gè)正整數(shù)N(1<=N<=100000)，代表兩個(gè)數(shù)組的長(zhǎng)度。

第二行有N個(gè)非負(fù)整數(shù)，范圍在0到1000000000之間，代表數(shù)組中的元素。

第三行有N個(gè)非負(fù)整數(shù)，范圍在0到1000000000之間，代表數(shù)組中的元素。

第四行有4個(gè)整數(shù)La,Ra,Lb,Rb，范圍在0到10^18之間，代表題目描述中的參數(shù)。

輸出：

輸出一個(gè)整數(shù)，代表所求的答案。

來(lái)自微眾銀行。

來(lái)自左程云。

答案2023-09-01：

大體過(guò)程如下：

1.定義兩個(gè)暴力方法（nums1和nums2）來(lái)求解問(wèn)題。這兩個(gè)方法的輸入?yún)?shù)包括兩個(gè)數(shù)組A和B，數(shù)組A的左右邊界（la和ra），數(shù)組B的左右邊界（lb和rb）。

2.方法nums1使用暴力的方法遍歷所有可能的區(qū)間，并統(tǒng)計(jì)滿足條件的區(qū)間個(gè)數(shù)。

• ??初始化變量ans為0，表示滿足條件的區(qū)間個(gè)數(shù)。

• ??使用兩層循環(huán)遍歷數(shù)組A的所有可能區(qū)間。外層循環(huán)變量l表示區(qū)間的左邊界，內(nèi)層循環(huán)變量r表示區(qū)間的右邊界。

• ??對(duì)于每個(gè)區(qū)間，初始化變量sumA和sumB為0，分別表示數(shù)組A和數(shù)組B中元素之和。

• ??使用一個(gè)循環(huán)遍歷當(dāng)前區(qū)間內(nèi)的元素，累加sumA和sumB。

• ??判斷sumA是否在[la, ra]之間，sumB是否在[lb, rb]之間，如果滿足條件則增加ans的值。

• ??返回ans作為結(jié)果。

3.方法nums2使用優(yōu)化的方法來(lái)求解問(wèn)題。

• ??初始化變量ans為0，表示滿足條件的區(qū)間個(gè)數(shù)。

• ??初始化變量rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2為0，分別表示數(shù)組A和數(shù)組B的右邊界和元素之和。

• ??使用一個(gè)循環(huán)遍歷數(shù)組A的所有可能左邊界。循環(huán)變量l表示左邊界的位置。

• ??在循環(huán)中，使用while循環(huán)更新rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2，使其滿足條件。

• ??計(jì)算數(shù)組A和數(shù)組B的左右交集的左邊界left和右邊界right。

• ??如果left小于right，則將right減去left的值加到ans中。

• ??根據(jù)當(dāng)前左邊界l更新rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2。

• ??返回ans作為結(jié)果。

4.定義randomArray方法，用于生成指定長(zhǎng)度和范圍的隨機(jī)數(shù)組。

• ??輸入?yún)?shù)包括數(shù)組的長(zhǎng)度n和隨機(jī)數(shù)的范圍v。

• ??初始化一個(gè)長(zhǎng)度為n的數(shù)組ans。

• ??使用一個(gè)循環(huán)遍歷數(shù)組，為每個(gè)元素賦一個(gè)隨機(jī)數(shù)值。

• ??返回生成的隨機(jī)數(shù)組ans。

5.定義max和min方法，分別用于求兩個(gè)數(shù)的最大值和最小值。

6.在main函數(shù)中進(jìn)行測(cè)試。

• ??初始化隨機(jī)數(shù)種子。

• ??定義常量N和V，表示數(shù)組的長(zhǎng)度和隨機(jī)數(shù)的范圍。

• ??定義變量testTimes，表示測(cè)試次數(shù)。

• ??使用循環(huán)進(jìn)行測(cè)試。

• ??在每次測(cè)試中，生成隨機(jī)數(shù)組A和B，以及隨機(jī)的la、ra、lb、rb。

• ??調(diào)用nums1和nums2方法，分別得到暴力和優(yōu)化方法的結(jié)果。

• ??比較兩個(gè)結(jié)果，如果不一致則輸出錯(cuò)誤信息。

• ??完成測(cè)試后輸出測(cè)試結(jié)束信息。

總的時(shí)間復(fù)雜度：

• ??對(duì)于方法nums1，需要三重循環(huán)遍歷數(shù)組，時(shí)間復(fù)雜度為O(n^3)。

• ??對(duì)于方法nums2，需要兩重循環(huán)遍歷數(shù)組，時(shí)間復(fù)雜度為O(n^2)。

總的額外空間復(fù)雜度：

• ??除了輸入?yún)?shù)外，額外使用的空間主要是變量和隨機(jī)數(shù)組。因此，額外空間復(fù)雜度為O(n)。

go完整代碼如下：

package?main

import?(
????"math/rand"
????"fmt"
????"time"
)

//?暴力方法
func?nums1(A?[]int,?B?[]int,?la?int,?ra?int,?lb?int,?rb?int)?int?{
????n?:=?len(A)
????ans?:=?0
????for?l?:=?0;?l?<?n;?l++?{
????????for?r?:=?l;?r?<?n;?r++?{
????????????sumA?:=?0
????????????sumB?:=?0
????????????for?i?:=?l;?i?<=?r;?i++?{
????????????????sumA?+=?A[i]
????????????????sumB?+=?B[i]
????????????}
????????????if?sumA?>=?la?&&?sumA?<=?ra?&&?sumB?>=?lb?&&?sumB?<=?rb?{
????????????????ans++
????????????}
????????}
????}
????return?ans
}

//?正式方法
func?nums2(A?[]int,?B?[]int,?la?int,?ra?int,?lb?int,?rb?int)?int?{
????n?:=?len(A)
????ans?:=?0
????rightA1,?sumA1,?rightA2,?sumA2?:=?0,?0,?0,?0
????rightB1,?sumB1,?rightB2,?sumB2?:=?0,?0,?0,?0
????for?l?:=?0;?l?<?n;?l++?{
????????for?rightA1?<?n?&&?sumA1+A[rightA1]?<?la?{
????????????sumA1?+=?A[rightA1]
????????????rightA1++
????????}
????????for?rightA2?<?n?&&?sumA2+A[rightA2]?<=?ra?{
????????????sumA2?+=?A[rightA2]
????????????rightA2++
????????}
????????for?rightB1?<?n?&&?sumB1+B[rightB1]?<?lb?{
????????????sumB1?+=?B[rightB1]
????????????rightB1++
????????}
????????for?rightB2?<?n?&&?sumB2+B[rightB2]?<=?rb?{
????????????sumB2?+=?B[rightB2]
????????????rightB2++
????????}
????????left?:=?max(rightA1,?rightB1)
????????right?:=?min(rightA2,?rightB2)
????????if?left?<?right?{
????????????ans?+=?right?-?left
????????}
????????if?rightA1?==?l?{
????????????rightA1++
????????}?else?{
????????????sumA1?-=?A[l]
????????}
????????sumA2?-=?A[l]
????????if?rightB1?==?l?{
????????????rightB1++
????????}?else?{
????????????sumB1?-=?B[l]
????????}
????????sumB2?-=?B[l]
????}
????return?ans
}

func?randomArray(n?int,?v?int)?[]int?{
????ans?:=?make([]int,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????ans[i]?=?rand.Intn(v)
????}
????return?ans
}

func?max(a?int,?b?int)?int?{
????if?a?>?b?{
????????return?a
????}
????return?b
}

func?min(a?int,?b?int)?int?{
????if?a?<?b?{
????????return?a
????}
????return?b
}

func?main()?{
????rand.Seed(time.Now().Unix())
????N?:=?50
????V?:=?100
????testTimes?:=?10000
????fmt.Println("測(cè)試開(kāi)始")
????for?i?:=?0;?i?<?testTimes;?i++?{
????????n?:=?rand.Intn(N)
????????A?:=?randomArray(n,?V)
????????B?:=?randomArray(n,?V)
????????a?:=?rand.Intn(V)
????????b?:=?rand.Intn(V)
????????c?:=?rand.Intn(V)
????????d?:=?rand.Intn(V)
????????la?:=?min(a,?b)
????????ra?:=?max(a,?b)
????????lb?:=?min(c,?d)
????????rb?:=?max(c,?d)
????????ans1?:=?nums1(A,?B,?la,?ra,?lb,?rb)
????????ans2?:=?nums2(A,?B,?la,?ra,?lb,?rb)
????????if?ans1?!=?ans2?{
????????????fmt.Println("出錯(cuò)了!")
????????}
????}
????fmt.Println("測(cè)試結(jié)束")
}

rust完整代碼如下：

use?rand::Rng;

fn?nums1(A:?&[i32],?B:?&[i32],?la:?i32,?ra:?i32,?lb:?i32,?rb:?i32)?->?i32?{
????let?n?=?A.len();
????let?mut?ans?=?0;
????for?l?in?0..n?{
????????for?r?in?l..n?{
????????????let?mut?sum_a?=?0;
????????????let?mut?sum_b?=?0;
????????????for?i?in?l..=r?{
????????????????sum_a?+=?A[i];
????????????????sum_b?+=?B[i];
????????????}
????????????if?sum_a?>=?la?&&?sum_a?<=?ra?&&?sum_b?>=?lb?&&?sum_b?<=?rb?{
????????????????ans?+=?1;
????????????}
????????}
????}
????ans
}

fn?nums2(A:?&[i32],?B:?&[i32],?la:?i32,?ra:?i32,?lb:?i32,?rb:?i32)?->?i32?{
????let?n?=?A.len()?as?i32;
????let?mut?ans?=?0;
????let?(mut?right_a1,?mut?sum_a1,?mut?right_a2,?mut?sum_a2)?=?(0,?0,?0,?0);
????let?(mut?right_b1,?mut?sum_b1,?mut?right_b2,?mut?sum_b2)?=?(0,?0,?0,?0);
????for?l?in?0..n?{
????????while?right_a1?<?n?&&?sum_a1?+?A[right_a1?as?usize]?<?la?{
????????????sum_a1?+=?A[right_a1?as?usize];
????????????right_a1?+=?1;
????????}
????????while?right_a2?<?n?&&?sum_a2?+?A[right_a2?as?usize]?<=?ra?{
????????????sum_a2?+=?A[right_a2?as?usize];
????????????right_a2?+=?1;
????????}
????????while?right_b1?<?n?&&?sum_b1?+?B[right_b1?as?usize]?<?lb?{
????????????sum_b1?+=?B[right_b1?as?usize];
????????????right_b1?+=?1;
????????}
????????while?right_b2?<?n?&&?sum_b2?+?B[right_b2?as?usize]?<=?rb?{
????????????sum_b2?+=?B[right_b2?as?usize];
????????????right_b2?+=?1;
????????}
????????let?left?=?right_a1.max(right_b1);
????????let?right?=?right_a2.min(right_b2);
????????if?left?<?right?{
????????????ans?+=?right?-?left;
????????}
????????if?right_a1?==?l?{
????????????right_a1?+=?1;
????????}?else?{
????????????sum_a1?-=?A[l?as?usize];
????????}
????????sum_a2?-=?A[l?as?usize];
????????if?right_b1?==?l?{
????????????right_b1?+=?1;
????????}?else?{
????????????sum_b1?-=?B[l?as?usize];
????????}
????????sum_b2?-=?B[l?as?usize];
????}
????ans
}

fn?random_array(n:?i32,?v:?i32)?->?Vec<i32>?{
????let?mut?rng?=?rand::thread_rng();
????(0..n).map(|_|?rng.gen_range(0,?v)).collect()
}

fn?main()?{
????const?N:?i32?=?50;
????const?V:?i32?=?100;
????const?TEST_TIMES:?usize?=?10000;
????println!("測(cè)試開(kāi)始");
????for?_?in?0..TEST_TIMES?{
????????let?n?=?rand::thread_rng().gen_range(0,?N);
????????let?A?=?random_array(n,?V);
????????let?B?=?random_array(n,?V);
????????let?a?=?rand::thread_rng().gen_range(0,?V);
????????let?b?=?rand::thread_rng().gen_range(0,?V);
????????let?c?=?rand::thread_rng().gen_range(0,?V);
????????let?d?=?rand::thread_rng().gen_range(0,?V);
????????let?la?=?a.min(b);
????????let?ra?=?a.max(b);
????????let?lb?=?c.min(d);
????????let?rb?=?c.max(d);
????????let?ans1?=?nums1(&A,?&B,?la,?ra,?lb,?rb);
????????let?ans2?=?nums2(&A,?&B,?la,?ra,?lb,?rb);
????????if?ans1?!=?ans2?{
????????????println!("出錯(cuò)了!");
????????}
????}
????println!("測(cè)試結(jié)束");
}


c++完整代碼如下：

#include?<iostream>
#include?<vector>
#include?<cstdlib>

using?namespace?std;

int?nums1(vector<int>&?A,?vector<int>&?B,?int?la,?int?ra,?int?lb,?int?rb)?{
????int?n?=?A.size();
????int?ans?=?0;
????for?(int?l?=?0;?l?<?n;?l++)?{
????????for?(int?r?=?l;?r?<?n;?r++)?{
????????????int?sumA?=?0;
????????????int?sumB?=?0;
????????????for?(int?i?=?l;?i?<=?r;?i++)?{
????????????????sumA?+=?A[i];
????????????????sumB?+=?B[i];
????????????}
????????????if?(sumA?>=?la?&&?sumA?<=?ra?&&?sumB?>=?lb?&&?sumB?<=?rb)?{
????????????????ans++;
????????????}
????????}
????}
????return?ans;
}

int?nums2(vector<int>&?A,?vector<int>&?B,?int?la,?int?ra,?int?lb,?int?rb)?{
????int?n?=?A.size();
????int?ans?=?0;
????int?rightA1?=?0,?sumA1?=?0,?rightA2?=?0,?sumA2?=?0,?rightB1?=?0,?sumB1?=?0,?rightB2?=?0,?sumB2?=?0;
????for?(int?l?=?0;?l?<?n;?l++)?{
????????while?(rightA1?<?n?&&?sumA1?+?A[rightA1]?<?la)?{
????????????sumA1?+=?A[rightA1++];
????????}
????????while?(rightA2?<?n?&&?sumA2?+?A[rightA2]?<=?ra)?{
????????????sumA2?+=?A[rightA2++];
????????}
????????while?(rightB1?<?n?&&?sumB1?+?B[rightB1]?<?lb)?{
????????????sumB1?+=?B[rightB1++];
????????}
????????while?(rightB2?<?n?&&?sumB2?+?B[rightB2]?<=?rb)?{
????????????sumB2?+=?B[rightB2++];
????????}
????????int?left?=?max(rightA1,?rightB1);
????????int?right?=?min(rightA2,?rightB2);
????????if?(left?<?right)?{
????????????ans?+=?right?-?left;
????????}
????????if?(rightA1?==?l)?{
????????????rightA1++;
????????}
????????else?{
????????????sumA1?-=?A[l];
????????}
????????sumA2?-=?A[l];
????????if?(rightB1?==?l)?{
????????????rightB1++;
????????}
????????else?{
????????????sumB1?-=?B[l];
????????}
????????sumB2?-=?B[l];
????}
????return?ans;
}

vector<int>?randomArray(int?n,?int?v)?{
????vector<int>?ans(n);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????ans[i]?=?rand()?%?v;
????}
????return?ans;
}

int?main()?{
????int?N?=?50;
????int?V?=?100;
????int?testTimes?=?10000;
????cout?<<?"測(cè)試開(kāi)始"?<<?endl;
????for?(int?i?=?0;?i?<?testTimes;?i++)?{
????????int?n?=?rand()?%?N;
????????vector<int>?A?=?randomArray(n,?V);
????????vector<int>?B?=?randomArray(n,?V);
????????int?a?=?rand()?%?V;
????????int?b?=?rand()?%?V;
????????int?c?=?rand()?%?V;
????????int?d?=?rand()?%?V;
????????int?la?=?min(a,?b);
????????int?ra?=?max(a,?b);
????????int?lb?=?min(c,?d);
????????int?rb?=?max(c,?d);
????????int?ans1?=?nums1(A,?B,?la,?ra,?lb,?rb);
????????int?ans2?=?nums2(A,?B,?la,?ra,?lb,?rb);
????????if?(ans1?!=?ans2)?{
????????????cout?<<?"出錯(cuò)了!"?<<?endl;
????????}
????}
????cout?<<?"測(cè)試結(jié)束"?<<?endl;

????return?0;
}

c完整代碼如下：

#include?<stdio.h>
#include?<stdlib.h>
#include?<time.h>

//?暴力方法
//?為了測(cè)試
int?nums1(int*?A,?int*?B,?int?n,?int?la,?int?ra,?int?lb,?int?rb)?{
????int?ans?=?0;
????for?(int?l?=?0;?l?<?n;?l++)?{
????????for?(int?r?=?l;?r?<?n;?r++)?{
????????????int?sumA?=?0;
????????????int?sumB?=?0;
????????????for?(int?i?=?l;?i?<=?r;?i++)?{
????????????????sumA?+=?A[i];
????????????????sumB?+=?B[i];
????????????}
????????????if?(sumA?>=?la?&&?sumA?<=?ra?&&?sumB?>=?lb?&&?sumB?<=?rb)?{
????????????????ans++;
????????????}
????????}
????}
????return?ans;
}

//?正式方法
//?時(shí)間復(fù)雜度O(N)
int?nums2(int*?A,?int*?B,?int?n,?int?la,?int?ra,?int?lb,?int?rb)?{
????int?ans?=?0;
????int?rightA1?=?0,?sumA1?=?0,?rightA2?=?0,?sumA2?=?0,?rightB1?=?0,?sumB1?=?0,?rightB2?=?0,?sumB2?=?0;
????for?(int?l?=?0;?l?<?n;?l++)?{
????????while?(rightA1?<?n?&&?sumA1?+?A[rightA1]?<?la)?{
????????????sumA1?+=?A[rightA1++];
????????}
????????while?(rightA2?<?n?&&?sumA2?+?A[rightA2]?<=?ra)?{
????????????sumA2?+=?A[rightA2++];
????????}
????????while?(rightB1?<?n?&&?sumB1?+?B[rightB1]?<?lb)?{
????????????sumB1?+=?B[rightB1++];
????????}
????????while?(rightB2?<?n&&?sumB2?+?B[rightB2]?<=?rb)?{
????????????sumB2?+=?B[rightB2++];
????????}
????????int?left?=?rightA1?>?rightB1???rightA1?:?rightB1;
????????int?right?=?rightA2?<?rightB2???rightA2?:?rightB2;
????????if?(left?<?right)?{
????????????ans?+=?right?-?left;
????????}
????????if?(rightA1?==?l)?{
????????????rightA1++;
????????}
????????else?{
????????????sumA1?-=?A[l];
????????}
????????sumA2?-=?A[l];
????????if?(rightB1?==?l)?{
????????????rightB1++;
????????}
????????else?{
????????????sumB1?-=?B[l];
????????}
????????sumB2?-=?B[l];
????}
????return?ans;
}

//?為了測(cè)試
int*?randomArray(int?n,?int?v)?{
????int*?ans?=?(int*)malloc(sizeof(int)?*?n);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????ans[i]?=?rand()?%?v;
????}
????return?ans;
}

//?為了測(cè)試
int?main()?{
????int?N?=?50;
????int?V?=?100;
????int?testTimes?=?10000;
????printf("測(cè)試開(kāi)始\n");
????srand(time(NULL));
????for?(int?i?=?0;?i?<?testTimes;?i++)?{
????????int?n?=?rand()?%?N;
????????int*?A?=?randomArray(n,?V);
????????int*?B?=?randomArray(n,?V);
????????int?a?=?rand()?%?V;
????????int?b?=?rand()?%?V;
????????int?c?=?rand()?%?V;
????????int?d?=?rand()?%?V;
????????int?la?=?(a?<?b)???a?:?b;
????????int?ra?=?(a?>?b)???a?:?b;
????????int?lb?=?(c?<?d)???c?:?d;
????????int?rb?=?(c?>?d)???c?:?d;
????????int?ans1?=?nums1(A,?B,?n,?la,?ra,?lb,?rb);
????????int?ans2?=?nums2(A,?B,?n,?la,?ra,?lb,?rb);
????????if?(ans1?!=?ans2)?{
????????????printf("出錯(cuò)了!\n");
????????}
????????free(A);
????????free(B);
????}
????printf("測(cè)試結(jié)束\n");
????return?0;
}