牛牛的数组匹配

[题目链接](https://www.nowcoder.com/practice/3d3406f4a7eb4346b025cc592be5b875)

思路

给定数组 (长度 )和数组 (长度 ),找出 中连续子数组之和与 最接近的那一段。若有多段同样接近,取起始位置最靠左的。

做法:前缀和 + 二分查找

)。

子数组 的和为 。我们需要找使 最小的 对,即对每个起点 ,在 中找最接近 的值。

由于题目保证数组元素均为正整数,前缀和严格递增,因此可以用二分查找 时间内定位最接近的位置。对每个 ,检查二分定位点及其左邻两个候选即可。

遍历所有起点 ,维护全局最小差值和对应的最左起始位置。

复杂度分析

  • 时间复杂度,对每个起点做一次二分查找。
  • 空间复杂度,存储前缀和数组。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    long long sumA = 0;
    for(int i = 0; i < n; i++){
        long long x; scanf("%lld", &x);
        sumA += x;
    }
    vector<long long> b(m);
    for(int i = 0; i < m; i++) scanf("%lld", &b[i]);

    vector<long long> pre(m+1, 0);
    for(int i = 0; i < m; i++) pre[i+1] = pre[i] + b[i];

    long long bestDiff = LLONG_MAX;
    int bestL = 0, bestR = 0;

    for(int i = 0; i < m; i++){
        long long target = sumA + pre[i];
        int lo = i+1, hi = m;
        int left = lo, right = hi;
        while(left <= right){
            int mid = (left + right) / 2;
            if(pre[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        for(int c = max(lo, left-1); c <= min(hi, left); c++){
            long long diff = abs(pre[c] - target);
            if(diff < bestDiff || (diff == bestDiff && i < bestL)){
                bestDiff = diff;
                bestL = i;
                bestR = c - 1;
            }
        }
    }

    for(int i = bestL; i <= bestR; i++){
        if(i > bestL) printf(" ");
        printf("%lld", b[i]);
    }
    printf("\n");
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        long sumA = 0;
        for (int i = 0; i < n; i++) sumA += sc.nextLong();
        long[] b = new long[m];
        for (int i = 0; i < m; i++) b[i] = sc.nextLong();

        long[] pre = new long[m + 1];
        for (int i = 0; i < m; i++) pre[i + 1] = pre[i] + b[i];

        long bestDiff = Long.MAX_VALUE;
        int bestL = 0, bestR = 0;

        for (int i = 0; i < m; i++) {
            long target = sumA + pre[i];
            int lo = i + 1, hi = m;
            int left = lo, right = hi;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (pre[mid] >= target) right = mid - 1;
                else left = mid + 1;
            }
            for (int c = Math.max(lo, left - 1); c <= Math.min(hi, left); c++) {
                long diff = Math.abs(pre[c] - target);
                if (diff < bestDiff || (diff == bestDiff && i < bestL)) {
                    bestDiff = diff;
                    bestL = i;
                    bestR = c - 1;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = bestL; i <= bestR; i++) {
            if (i > bestL) sb.append(' ');
            sb.append(b[i]);
        }
        System.out.println(sb.toString());
    }
}
import bisect, sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    sumA = sum(a)

    pre = [0] * (m + 1)
    for i in range(m):
        pre[i + 1] = pre[i] + b[i]

    best_diff = float('inf')
    best_l = 0
    best_r = 0

    for i in range(m):
        target = sumA + pre[i]
        lo = i + 1
        pos = bisect.bisect_left(pre, target, lo, m + 1)
        for c in range(max(lo, pos - 1), min(m, pos) + 1):
            diff = abs(pre[c] - target)
            if diff < best_diff or (diff == best_diff and i < best_l):
                best_diff = diff
                best_l = i
                best_r = c - 1

    print(' '.join(map(str, b[best_l:best_r + 1])))

main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);
    const b = lines[2].split(' ').map(Number);

    let sumA = 0;
    for (let i = 0; i < n; i++) sumA += a[i];

    const pre = new Array(m + 1).fill(0);
    for (let i = 0; i < m; i++) pre[i + 1] = pre[i] + b[i];

    let bestDiff = Infinity;
    let bestL = 0, bestR = 0;

    for (let i = 0; i < m; i++) {
        const target = sumA + pre[i];
        let lo = i + 1, hi = m;
        let left = lo, right = hi;
        while (left <= right) {
            const mid = (left + right) >> 1;
            if (pre[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        for (let c = Math.max(lo, left - 1); c <= Math.min(hi, left); c++) {
            const diff = Math.abs(pre[c] - target);
            if (diff < bestDiff || (diff === bestDiff && i < bestL)) {
                bestDiff = diff;
                bestL = i;
                bestR = c - 1;
            }
        }
    }

    const res = [];
    for (let i = bestL; i <= bestR; i++) res.push(b[i]);
    console.log(res.join(' '));
});