2023-09-01：用go语言编写。给出两个长度均为n的数组，
A = { a1, a2, ... ,an }，
B = { b1, b2, ... ,bn }。
你需要求出其有多少个区间[L,R]满足:
数组A中下标在[L,R]中的元素之和在[La,Ra]之中，
数组B中下标在[L,R]中的元素之和在[Lb,Rb]之中。
输入：
第一行有一个正整数N(1<=N<=100000)，代表两个数组的长度。
第二行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。
第三行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。
第四行有4个整数La,Ra,Lb,Rb，范围在0到10^18之间，代表题目描述中的参数。
输出：
输出一个整数，代表所求的答案。
来自微众银行。
来自左程云。
答案2023-09-01：
大体过程如下：
1.定义两个暴力方法（nums1和nums2）来求解问题。这两个方法的输入参数包括两个数组A和B，数组A的左右边界（la和ra），数组B的左右边界（lb和rb）。
2.方法nums1使用暴力的方法遍历所有可能的区间，并统计满足条件的区间个数。
初始化变量ans为0，表示满足条件的区间个数。
使用两层循环遍历数组A的所有可能区间。外层循环变量l表示区间的左边界，内层循环变量r表示区间的右边界。
对于每个区间，初始化变量sumA和sumB为0，分别表示数组A和数组B中元素之和。
使用一个循环遍历当前区间内的元素，累加sumA和sumB。
判断sumA是否在[la, ra]之间，sumB是否在[lb, rb]之间，如果满足条件则增加ans的值。
返回ans作为结果。
3.方法nums2使用优化的方法来求解问题。
初始化变量ans为0，表示满足条件的区间个数。
初始化变量rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2为0，分别表示数组A和数组B的右边界和元素之和。
使用一个循环遍历数组A的所有可能左边界。循环变量l表示左边界的位置。
在循环中，使用while循环更新rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2，使其满足条件。
计算数组A和数组B的左右交集的左边界left和右边界right。
如果left小于right，则将right减去left的值加到ans中。
根据当前左边界l更新rightA1、sumA1、rightA2、sumA2、rightB1、sumB1、rightB2、sumB2。
返回ans作为结果。
4.定义randomArray方法，用于生成指定长度和范围的随机数组。
输入参数包括数组的长度n和随机数的范围v。
初始化一个长度为n的数组ans。
使用一个循环遍历数组，为每个元素赋一个随机数值。
返回生成的随机数组ans。
5.定义max和min方法，分别用于求两个数的最大值和最小值。
6.在main函数中进行测试。
初始化随机数种子。
定义常量N和V，表示数组的长度和随机数的范围。
定义变量testTimes，表示测试次数。
使用循环进行测试。
在每次测试中，生成随机数组A和B，以及随机的la、ra、lb、rb。
调用nums1和nums2方法，分别得到暴力和优化方法的结果。
比较两个结果，如果不一致则输出错误信息。
完成测试后输出测试结束信息。
总的时间复杂度：
对于方法nums1，需要三重循环遍历数组，时间复杂度为O(n^3)。
对于方法nums2，需要两重循环遍历数组，时间复杂度为O(n^2)。
总的额外空间复杂度：
除了输入参数外，额外使用的空间主要是变量和随机数组。因此，额外空间复杂度为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("测试开始")
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("出错了!")
}
}
fmt.Println("测试结束")
}
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
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!("测试开始");
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!("出错了!");
}
}
println!("测试结束");
}
c++完整代码如下：
#include
#include
#include
using namespace std;
int nums1(vector
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 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
vector
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 << "测试开始" << endl;
for (int i = 0; i < testTimes; i++) {
int n = rand() % N;
vector
vector
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 << "出错了!" << endl;
}
}
cout << "测试结束" << endl;
return 0;
}
c完整代码如下：
#include
#include
#include
// 暴力方法
// 为了测试
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;
}
// 正式方法
// 时间复杂度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;
}
// 为了测试
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;
}
// 为了测试
int main() {
int N = 50;
int V = 100;
int testTimes = 10000;
printf("测试开始\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("出错了!\n");
}
free(A);
free(B);
}
printf("测试结束\n");
return 0;
}
相关阅读
发表评论