前缀和+哈希表思路:将输入数组中的元素减去k可将题目转化为“和为0的最长连续子数组”。进一步,为省去重复计算,使用前缀和处理数组。使用哈希表记录前缀和数组中每个值第一次出现的位置,遍历数组找到相同的值便计算距离并更新最大值即可。上述前缀和数组可优化为一个变量。python参考代码:import sysfrom itertools import *a = []for line in sys.stdin:    a += line.split()a = list(map(int, a))n, k = a[0], a[1]a = a[2:]for i in range(n): a[i] -= ka = list(accumulate(a, initial = 0))s = {}ans = -1for i, v in enumerate(a):    if v not in s: s[v] = i    else: ans = max(ans, i - s[v])print(ans)Java参考代码:import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息public class Main {    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int n = in.nextInt(), k = in.nextInt();        long[] nums = new long[n + 1];        int i = 0, ans = -1;        Map<Long, Integer> map = new HashMap<>();        map.put(0L, 0);        // 注意 hasNext 和 hasNextLine 的区别        while (in.hasNextInt()) { // 注意 while 处理多个 case            nums[++i] += in.nextInt() - k + nums[i - 1];            if(!map.containsKey(nums[i])) map.put(nums[i], i);            else ans = Math.max(ans, i - map.get(nums[i]));        }        System.out.println(ans);    }}Java前缀和优化:import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息public class Main {    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int n = in.nextInt(), k = in.nextInt();        long s = 0;        int ans = -1;        Map<Long, Integer> map = new HashMap<>();        map.put(0L, 0);        // 注意 hasNext 和 hasNextLine 的区别        for (int i = 1; i <= n; i++) { // 注意 while 处理多个 case            s += in.nextInt() - k;            if(!map.containsKey(s)) map.put(s, i);            else ans = Math.max(ans, i - map.get(s));        }        System.out.println(ans);    }}
点赞 2
评论 1
全部评论

相关推荐

点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务