2023-09-01：用go语言编写。给出两个长度均为n的数组， A = { a1, a2, ... ,an }， B = { b1, b2, ... ,bn }。你需要求出其有多少个区间[L,R]

阅读原文时间：2023年09月02日阅读：4

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<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!("测试开始");
    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 <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 << "测试开始" << 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 << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}

c完整代码如下：

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

// 暴力方法
// 为了测试
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;
}