平均数为k的最长连续子数组

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

int main(){
    int n ,k;
    cin >>n >>k;
    vector<int> a(n,0);
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }

    unordered_map<long, int> ump;
    ump[0] = -1;
    int start = 0;
    long long sum = 0;
    int maxlen = -1;
    for(int i = 0; i < a.size(); i++){
        sum += a[i] - k;
        if(ump.find(sum ) != ump.end()){
            maxlen = max(maxlen, i- ump[sum]);
        }else{
            ump[sum] = i;
        }
    }
    cout<<maxlen<<endl;
    return 0;
}

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


// 平均数不好处理，每个数减k转化为计算和为0的最长子数组
int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        vector<int> nums(a);
        int res = -1;
         long long sum = 0;
        for (int i = 0; i < a; ++i) {
            cin >> nums[i];
            nums[i] -= b;
        }
        unordered_map<long long, int> mp;
        mp[0] = -1;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            if (mp.count(sum)) {
                res = max(res, i - mp[sum]);
            }
            if (!mp.count(sum)) {
                mp[sum] = i;
            }
        }
        cout << res;
    }
}

#include <iostream>
#include<map>;
using namespace std;

int main() {
    /*
        思路:
        1.既然要求平均数为k,只需把所有元素减去k,若一些元素和为0即说明这些元素平均数为k
        2.使用map<sum,i>表示前i个位置的和
        3.遍历元素进行求和。
            当出现不存在的sum时进行记录
            当出现已存在的sum时,假设此时下标为j，记录sum下标为i
            则说明在(i+1,j)这一段所有元素的和为0,即其平均数是k,是符合要求的
        4.找出最长的子数组即可
        
    */
    long n,k;
    cin>>n>>k;

    int res = -1;
    
    map<long long,int> sumMp;
    sumMp[0] = 0;


    long long sum = 0;
    long ai;
    for(int i = 1; i <= n; i++)
    {
        cin >> ai;
        sum += ai-k;

        if(sumMp.count(sum))
        {
            res = max(res, i - sumMp[sum]);
        }
        else
        {
            sumMp[sum] = i;
        }

    }

    cout<<res;
    return 0;

}
// 64 位输出请用 printf("%lld")

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt(), ans = -1;
        long res = 0;
        int[] a = new int[n+5];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        Map<Long, Integer> b = new HashMap<>();
        b.put(0L, 0);
        for (int i = 1; i <= n; i++) {
            res += a[i] - k;
            if (b.containsKey(res)) {
                ans = Math.max(ans, i - b.get(res));
            } else {
                b.put(res, i);
            }
        }
        System.out.print(ans);
    }
}

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bf.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        long k = Long.parseLong(str[1]);

        str = bf.readLine().split(" ");
        //多个元素的平均数为k，那么对每个元素都-k，得到的元素之和一定为0，即子数组之和为0
        //子数组之和为0，那么对应的前缀和数组sum，一定有两个下标ij，sum[i]==sum[j]
        long[] nums = new long[n];
        for(int i=0;i<n;i++){
            nums[i]=Long.parseLong(str[i])-k;
        }

        long[] sums = new long[n+1];
        Map<Long, List<Integer>> sum2Index = new HashMap<>();
        for(int i=1;i<=n;i++){
            sums[i]=sums[i-1]+nums[i-1];
            List<Integer> oldValue = sum2Index.computeIfAbsent(sums[i], e->new ArrayList<>());
            oldValue.add(i);
        }
        //System.out.println(sum2Index);

        int res =-1;
        for(Long sum : sum2Index.keySet()){
            if(sum==0){//如果前缀和为0，那么[0,i]就是一个满足条件的结果了
                int curr = Collections.max(sum2Index.get(sum));
                res=Math.max(res, curr);
                continue;
            }
            if(sum2Index.get(sum).size()>=2){
                List<Integer> list = sum2Index.get(sum);
                int min=list.get(0);
                int max = list.get(0);
                for(int i=0;i<list.size();i++){
                    min = Math.min(min, list.get(i));
                    max = Math.max(max, list.get(i));
                }
                res=Math.max(res, (max-min));
            }
        }
        System.out.println(res);


    }
}