题解 | #平均数为k的最长连续子数组#
平均数为k的最长连续子数组
https://www.nowcoder.com/practice/2e47f99735584ac5ba30d75ac14d6524
前缀和+哈希表
思路:
- 将输入数组中的元素减去k可将题目转化为“和为0的最长连续子数组”。
- 进一步,为省去重复计算,使用前缀和处理数组。
- 使用哈希表记录前缀和数组中每个值第一次出现的位置,遍历数组找到相同的值便计算距离并更新最大值即可。
- 上述前缀和数组可优化为一个变量。
python参考代码:
import sys from 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] -= k a = list(accumulate(a, initial = 0)) s = {} ans = -1 for 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); } }