题目（力扣式）

80XX. 找到最接＊＊＊均数 k 的连续子数组区间

难度：中等

题目描述

给定一个正整数数组  nums  和一个目标值  k ，请你找到一段连续非空子数组，使其平均值最接近 k。

题目保证有唯一最优解。

返回其下标区间 [left, right]（下标从 0 开始）。

数据范围

-  1 <= nums.length <= 1e5 

​

-  1 <= nums[i] <= 1e4 

​

-  1 <= k <= 1e4 

 

核心思路（你要的二分逻辑）

1. 前缀和预处理

​

2. 对每个右端点 i，计算目标前缀值

​

3. 二分查找前面已存的前缀，找最接近目标的位置

​

4. 用 check 比较差值，更新最优区间

…

typedef long long ll;

class Solution {

public:

vector<int> getClosestSubarray(vector<int>& nums, double k) {

int n = nums.size();

// 存：前缀和，下标

vector<pair<ll, int>> pre;

pre.emplace_back(0, -1);

ll sum = 0;

double best = 1e18;

int l = 0, r = 0;

for (int i = 0; i < n; ++i) {

sum += nums[i];

// 目标：找 pre[j] 最接近 sum - k*(i+1)

double target = sum - k * (i + 1);

// 二分找插入位置

int pos = lower_bound(pre.begin(), pre.end(), make_pair(target, -1)) - pre.begin();

// 检查 pos-1 和 pos（最接近的两个）

for (int d : {-1, 0}) {

int j = pos + d;

if (j >= 0 && j < pre.size()) {

// check：计算当前差值是否更优

if (check(sum, pre[j].first, i - pre[j].second, k, best)) {

best = fabs((sum - pre[j].first) * 1.0 / (i - pre[j].second) - k);

l = pre[j].second + 1;

r = i;

}

}

}

// 插入并保持有序

pre.emplace_back(sum, i);

sort(pre.begin(), pre.end());

}

return {l, r};

}

// check 函数：判断当前子数组是否更优

bool check(ll s, ll pj, int len, double k, double best) {

double now = fabs((s - pj) * 1.0 / len - k);

return now < best;

}

};

…