企业官网建设流程全解析

LeetCode 题解：Maximum Frequency After Subarray Operation 子数组操作最大化 k 的频率（暴力枚举 / Kadane / 哈希表单趟扫描）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文围绕本仓库 articles/maximum-frequency-after-subarray-operation.md 所讲解的经典题解展开：给定一个数组，允许执行一次"选取某个连续子数组，对其内每个元素加上同一个常数"的操作，目标是让某个目标值k在整个数组中出现的次数尽可能多。文章从暴力枚举讲起，逐步演进到基于 Kadane 算法（最大子数组和）的线性解法，再到利用哈希表将全部候选值压缩成单趟扫描的最终形态，并给出暴力法、两版 Kadane 实现的完整多语言代码与复杂度分析。读完本文，你将掌握"把子数组操作问题转化为最大净收益子数组问题"的建模思路，并能独立实现、分析和验证该题的三种解法。

一、问题本质与前置知识

问题重述

• 输入：整数数组nums与目标值k。
• 操作：至多执行一次 —— 选取任意连续子数组[l, r]，将其中每一个元素统一加上同一个常数（可为任意整数，也可为 0，操作可选可不选）。
• 目标：最大化操作后数组里等于k的元素个数。

从题解代码中的循环范围num in 1..50（以及k本身属于该值域）可以推断，本题的约束为元素取值限定在1到50之间，这也是暴力法得以枚举全部候选值的前提。这一点在仓库 articles/maximum-frequency-after-subarray-operation.md 的暴力解法中体现得最直接：外层循环遍历1..50的所有候选值。

前置知识（Prerequisites）

原文档明确要求读者先掌握以下三点，本仓库恰好都有对应题解可对照学习：

仓库中 python/0053-maximum-subarray.py 给出的经典 Kadane 实现如下，它是理解本文解法二、解法三的基石：

class Solution: def maxSubArray(self, nums: List[int]) -> int: res = nums[0] total = 0 for n in nums: total += n res = max(res, total) if total < 0: total = 0 return res

关键就在if total < 0: total = 0这一步——运行和一旦为负就归零重来，等价于"放弃前面的元素，从当前位置重新开始一个子数组"。本文解法二正是把这一思想从"求和"移植到"计数净收益"上。

二、解法一：暴力枚举（Brute Force）

核心思路（Intuition）

操作允许我们选取一个子数组并对其内每个元素加上同一个常数。要最大化某个值k的出现次数，最直接的想法是：选定某个候选值num，挑一个常数把它变成k（即常数= k - num），然后遍历所有可能的子数组：

• 子数组内的每个num都会变成k，收益+1；
• 但子数组内原本是k的元素会被改成别的值，损失-1；
• 最终频率 = 原始k的总数cntK+ 该子数组带来的净收益。

由于值域只有 50，外层枚举num（1到50，跳过k），内层枚举所有起点i与终点j即可。

算法步骤

1. 统计k在原数组中的出现次数，记为cntK。
2. 对每个候选值num（1到50，跳过k）：
   • 对每个起点i：
     • 用临时变量保存cntK，置cnt = 0；
     • 从j = i向后扫描：遇到num则cnt += 1（它会被转换成k）；遇到k则cntK -= 1（它会被改成别的值）；
     • 每步用cnt + cntK更新答案；
     • 扫描结束后把cntK恢复为临时值，避免污染下一个起点。
3. 返回过程中的最大频率。

多语言实现

Python

class Solution: def maxFrequency(self, nums: List[int], k: int) -> int: n = len(nums) cntK = nums.count(k) res = cntK for num in range(1, 51): if num == k: continue for i in range(n): tmp, cnt = cntK, 0 for j in range(i, n): if nums[j] == num: cnt += 1 elif nums[j] == k: cntK -= 1 res = max(res, cnt + cntK) cntK = tmp return res

Java

public class Solution { public int maxFrequency(int[] nums, int k) { int n = nums.length; int cntK = 0; for (int x : nums) if (x == k) cntK++; int res = cntK; for (int num = 1; num <= 50; num++) { if (num == k) continue; for (int i = 0; i < n; i++) { int tmp = cntK; int cnt = 0; for (int j = i; j < n; j++) { if (nums[j] == num) { cnt++; } else if (nums[j] == k) { cntK--; } res = Math.max(res, cnt + cntK); } cntK = tmp; } } return res; } }

C++

class Solution { public: int maxFrequency(vector<int>& nums, int k) { int n = nums.size(); int cntK = 0; for (int x : nums) if (x == k) cntK++; int res = cntK; for (int num = 1; num <= 50; num++) { if (num == k) continue; for (int i = 0; i < n; i++) { int tmp = cntK, cnt = 0; for (int j = i; j < n; j++) { if (nums[j] == num) { cnt++; } else if (nums[j] == k) { cntK--; } res = max(res, cnt + cntK); } cntK = tmp; } } return res; } };

JavaScript

class Solution { /** * @param {number[]} nums * @param {number} k * @return {number} */ maxFrequency(nums, k) { const n = nums.length; let cntK = nums.filter((x) => x === k).length; let res = cntK; for (let num = 1; num <= 50; num++) { if (num === k) continue; for (let i = 0; i < n; i++) { const tmp = cntK; let cnt = 0; for (let j = i; j < n; j++) { if (nums[j] === num) { cnt++; } else if (nums[j] === k) { cntK--; } res = Math.max(res, cnt + cntK); } cntK = tmp; } } return res; } }

C#

public class Solution { public int MaxFrequency(int[] nums, int k) { int n = nums.Length; int cntK = 0; foreach (var x in nums) if (x == k) cntK++; int res = cntK; for (int num = 1; num <= 50; num++) { if (num == k) continue; for (int i = 0; i < n; i++) { int tmp = cntK; int cnt = 0; for (int j = i; j < n; j++) { if (nums[j] == num) { cnt++; } else if (nums[j] == k) { cntK--; } res = Math.Max(res, cnt + cntK); } cntK = tmp; } } return res; } }

Go

func maxFrequency(nums []int, k int) int { n := len(nums) cntK := 0 for _, x := range nums { if x == k { cntK++ } } res := cntK for num := 1; num <= 50; num++ { if num == k { continue } for i := 0; i < n; i++ { tmp := cntK cnt := 0 for j := i; j < n; j++ { if nums[j] == num { cnt++ } else if nums[j] == k { cntK-- } if cnt+cntK > res { res = cnt + cntK } } cntK = tmp } } return res }

Kotlin

class Solution { fun maxFrequency(nums: IntArray, k: Int): Int { val n = nums.size var cntK = nums.count { it == k } var res = cntK for (num in 1..50) { if (num == k) continue for (i in 0 until n) { val tmp = cntK var cnt = 0 for (j in i until n) { if (nums[j] == num) { cnt++ } else if (nums[j] == k) { cntK-- } res = maxOf(res, cnt + cntK) } cntK = tmp } } return res } }

Swift

class Solution { func maxFrequency(_ nums: [Int], _ k: Int) -> Int { let n = nums.count var cntK = nums.filter { $0 == k }.count var res = cntK for num in 1...50 { if num == k { continue } for i in 0..<n { let tmp = cntK var cnt = 0 for j in i..<n { if nums[j] == num { cnt += 1 } else if nums[j] == k { cntK -= 1 } res = max(res, cnt + cntK) } cntK = tmp } } return res } }

Rust

impl Solution { pub fn max_frequency(nums: Vec<i32>, k: i32) -> i32 { let n = nums.len(); let mut cnt_k = nums.iter().filter(|&&x| x == k).count() as i32; let mut res = cnt_k; for num in 1..=50 { if num == k { continue; } for i in 0..n { let tmp = cnt_k; let mut cnt = 0; for j in i..n { if nums[j] == num { cnt += 1; } else if nums[j] == k { cnt_k -= 1; } res = res.max(cnt + cnt_k); } cnt_k = tmp; } } res } }

复杂度分析

• 时间复杂度：$O(50 \times n^2)$ —— 50 个候选值，每个候选值要枚举 $O(n^2)$ 个子数组。
• 空间复杂度：$O(1)$ —— 只使用常数个变量。

暴力法在n较大时无法通过，但它完整刻画了问题的净收益模型，是后两种优化的正确性基准。

三、解法二：Kadane 算法（逐目标线性扫描）

核心思路（Intuition）

暴力法枚举了所有子数组，但我们可以借用 Kadane 算法在单次线性扫描内找到"最佳子数组"。对固定的目标值num，把数组做如下映射：

• num视为+1（操作后我们会多得到一个k）；
• k视为-1（操作后我们会失去一个k）；
• 其余元素视为0（不受影响）。

于是"转换num为k的净收益"就等于该映射序列中最大子数组和，这正是 Kadane 算法能线性求解的问题。对每个候选值各跑一遍 Kadane，总复杂度 $O(50 \times n)$。

算法步骤

1. 统计k出现的次数cntK。
2. 对每个候选值i（1到50，跳过k）：
   • 初始化cnt = 0；
   • 线性扫描数组：遇到i则cnt += 1，遇到k则cnt -= 1；
   • 若cnt变成负数则重置为0（Kadane 重置，等价于"空子数组 / 不选"）；
   • 每步用cntK + cnt更新答案。
3. 返回最大频率。

多语言实现

Python

class Solution: def maxFrequency(self, nums: List[int], k: int) -> int: cntK = nums.count(k) res = 0 for i in range(1, 51): if i == k: continue cnt = 0 for num in nums: if num == i: cnt += 1 if num == k: cnt -= 1 cnt = max(cnt, 0) res = max(res, cntK + cnt) return res

Java

public class Solution { public int maxFrequency(int[] nums, int k) { int cntK = 0; for (int num : nums) { if (num == k) cntK++; } int res = 0; for (int i = 1; i <= 50; i++) { if (i == k) continue; int cnt = 0; for (int num : nums) { if (num == i) cnt++; if (num == k) cnt--; cnt = Math.max(cnt, 0); res = Math.max(res, cntK + cnt); } } return res; } }

C++

class Solution { public: int maxFrequency(vector<int>& nums, int k) { int cntK = 0; for (int num : nums) { if (num == k) cntK++; } int res = 0; for (int i = 1; i <= 50; i++) { if (i == k) continue; int cnt = 0; for (int num : nums) { if (num == i) cnt++; if (num == k) cnt--; cnt = max(cnt, 0); res = max(res, cntK + cnt); } } return res; } };

JavaScript

class Solution { /** * @param {number[]} nums * @param {number} k * @return {number} */ maxFrequency(nums, k) { let cntK = 0; for (const num of nums) { if (num === k) cntK++; } let res = 0; for (let i = 1; i <= 50; i++) { if (i === k) continue; let cnt = 0; for (const num of nums) { if (num === i) cnt++; if (num === k) cnt--; cnt = Math.max(cnt, 0); res = Math.max(res, cntK + cnt); } } return res; } }

C#

public class Solution { public int MaxFrequency(int[] nums, int k) { int cntK = 0; foreach (var num in nums) { if (num == k) cntK++; } int res = 0; for (int i = 1; i <= 50; i++) { if (i == k) continue; int cnt = 0; foreach (var num in nums) { if (num == i) cnt++; if (num == k) cnt--; cnt = Math.Max(cnt, 0); res = Math.Max(res, cntK + cnt); } } return res; } }

Go

func maxFrequency(nums []int, k int) int { cntK := 0 for _, num := range nums { if num == k { cntK++ } } res := 0 for i := 1; i <= 50; i++ { if i == k { continue } cnt := 0 for _, num := range nums { if num == i { cnt++ } if num == k { cnt-- } if cnt < 0 { cnt = 0 } if cntK+cnt > res { res = cntK + cnt } } } return res }

Kotlin

class Solution { fun maxFrequency(nums: IntArray, k: Int): Int { val cntK = nums.count { it == k } var res = 0 for (i in 1..50) { if (i == k) continue var cnt = 0 for (num in nums) { if (num == i) cnt++ if (num == k) cnt-- cnt = maxOf(cnt, 0) res = maxOf(res, cntK + cnt) } } return res } }

Swift

class Solution { func maxFrequency(_ nums: [Int], _ k: Int) -> Int { let cntK = nums.filter { $0 == k }.count var res = 0 for i in 1...50 { if i == k { continue } var cnt = 0 for num in nums { if num == i { cnt += 1 } if num == k { cnt -= 1 } cnt = max(cnt, 0) res = max(res, cntK + cnt) } } return res } }

Rust

impl Solution { pub fn max_frequency(nums: Vec<i32>, k: i32) -> i32 { let cnt_k = nums.iter().filter(|&&x| x == k).count() as i32; let mut res = 0; for i in 1..=50 { if i == k { continue; } let mut cnt = 0; for &num in &nums { if num == i { cnt += 1; } if num == k { cnt -= 1; } cnt = cnt.max(0); res = res.max(cnt_k + cnt); } } res } }

复杂度分析

• 时间复杂度：$O(50 \times n)$ —— 每个候选值各做一次线性 Kadane 扫描。
• 空间复杂度：$O(1)$。

与 python/0053-maximum-subarray.py 的经典 Kadane 对比可以发现，本题的解只是把"累加元素值"换成了"累加映射后的 +1/-1/0"，并把"求最大和"换成了"求最大净收益cnt"，其余结构完全同构。

四、解法三：Kadane 算法 + 哈希表单趟扫描（最优解）

核心思路（Intuition）

解法二仍要对 50 个候选值各扫一遍数组。观察发现：所有候选值可以同时在一趟扫描内处理。对于每个数字num，我们维护"以当前位置结尾、用于把num转换成k的最佳运行和"cnt[num]。当遇到一个num时，它对应的子数组既可以接续之前的最佳状态，也可以从当前位置重新开始（重新开始时以k的计数为基准，因为从k处开始意味着放弃前面的元素）。于是递推式：

cnt[num] = max(cnt[num], cnt[k]) + 1

其中cnt[k]表示当前已经累计的k的计数。每步用cnt[num] - cnt[k]记录"当前净收益"，res保存全局最大净收益，最终答案是cnt[k] + res。

算法步骤

1. 维护哈希表cnt：cnt[num]表示"以当前位置结尾、把num转换为k的最佳运行和"。
2. 单趟扫描数组，对每个元素num：
   • 更新cnt[num] = max(cnt[num], cnt[k]) + 1；
   • 用cnt[num] - cnt[k]更新全局最大净收益res。
3. 返回cnt[k] + res。

多语言实现

Python

class Solution: def maxFrequency(self, nums: List[int], k: int) -> int: cnt = defaultdict(int) res = 0 for num in nums: cnt[num] = max(cnt[num], cnt[k]) + 1 res = max(res, cnt[num] - cnt[k]) return cnt[k] + res

Java

public class Solution { public int maxFrequency(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); int res = 0; for (int num : nums) { int prev = Math.max(cnt.getOrDefault(num, 0), cnt.getOrDefault(k, 0)); cnt.put(num, prev + 1); res = Math.max(res, cnt.get(num) - cnt.getOrDefault(k, 0)); } return cnt.getOrDefault(k, 0) + res; } }

C++

class Solution { public: int maxFrequency(vector<int>& nums, int k) { unordered_map<int,int> cnt; int res = 0; for (int num : nums) { int prev = max(cnt[num], cnt[k]); cnt[num] = prev + 1; res = max(res, cnt[num] - cnt[k]); } return cnt[k] + res; } };

JavaScript

class Solution { /** * @param {number[]} nums * @param {number} k * @return {number} */ maxFrequency(nums, k) { const cnt = new Map(); let res = 0; for (const num of nums) { const prev = Math.max(cnt.get(num) || 0, cnt.get(k) || 0); cnt.set(num, prev + 1); res = Math.max(res, cnt.get(num) - (cnt.get(k) || 0)); } return (cnt.get(k) || 0) + res; } }

C#

public class Solution { public int MaxFrequency(int[] nums, int k) { var cnt = new Dictionary<int,int>(); int res = 0; foreach (var num in nums) { int prev = Math.Max( cnt.TryGetValue(num, out var cn) ? cn : 0, cnt.TryGetValue(k, out var ck) ? ck : 0 ); cnt[num] = prev + 1; res = Math.Max(res, cnt[num] - (cnt.TryGetValue(k, out ck) ? ck : 0)); } return (cnt.TryGetValue(k, out var ckk) ? ckk : 0) + res; } }

Go

func maxFrequency(nums []int, k int) int { cnt := make(map[int]int) res := 0 for _, num := range nums { prev := cnt[num] if cnt[k] > prev { prev = cnt[k] } cnt[num] = prev + 1 if cnt[num]-cnt[k] > res { res = cnt[num] - cnt[k] } } return cnt[k] + res }

Kotlin

class Solution { fun maxFrequency(nums: IntArray, k: Int): Int { val cnt = mutableMapOf<Int, Int>() var res = 0 for (num in nums) { val prev = maxOf(cnt.getOrDefault(num, 0), cnt.getOrDefault(k, 0)) cnt[num] = prev + 1 res = maxOf(res, cnt[num]!! - cnt.getOrDefault(k, 0)) } return cnt.getOrDefault(k, 0) + res } }

Swift

class Solution { func maxFrequency(_ nums: [Int], _ k: Int) -> Int { var cnt = [Int: Int]() var res = 0 for num in nums { let prev = max(cnt[num, default: 0], cnt[k, default: 0]) cnt[num] = prev + 1 res = max(res, cnt[num]! - cnt[k, default: 0]) } return cnt[k, default: 0] + res } }

Rust

impl Solution { pub fn max_frequency(nums: Vec<i32>, k: i32) -> i32 { let mut cnt = HashMap::new(); let mut res = 0; for &num in &nums { let prev = *cnt.get(&num).unwrap_or(&0).max(cnt.get(&k).unwrap_or(&0)); *cnt.entry(num).or_insert(0) = prev + 1; res = res.max(cnt[&num] - cnt.get(&k).unwrap_or(&0)); } *cnt.get(&k).unwrap_or(&0) + res } }

复杂度分析

• 时间复杂度：$O(n)$ —— 全程只扫描数组一次。
• 空间复杂度：$O(50)$ —— 哈希表最多容纳 50 种取值。

res初始为0是关键：它表示"不选任何子数组（空子数组）"时净收益为 0，天然覆盖了"不做操作"的基准情形。

五、常见陷阱（Common Pitfalls）

1. 误解子数组操作

操作是对所选子数组内每一个元素加上同一个常数，而不是选择性修改其中部分元素。这意味着子数组[l, r]内同时存在k和num时，把num变成k的同时，原本的k也必然被改成别的值——收益与损失必须一起结算。

2. 忘记扣除损失的 k 值

把num转成k时，子数组内原有的每个k都会变成k + constant而不再是k。正确的净收益公式是：

净收益 = (子数组内 num 的个数) - (子数组内 k 的个数)

只数收益、不扣损失（或扣得不对）的实现必然得到错误答案。

3. 在候选值之间未重置状态

解法二在遍历1..50的每个目标值时，都必须独立地跑一遍 Kadane：每个候选值开始前要cnt = 0。若不在候选值之间重置运行计数，前一个候选值累积的状态会污染下一个候选值的最大子数组计算。

4. 忽略"不做操作"的情形

操作是可选的。当k原本出现次数就很多时，最优策略可能是完全不动数组。答案的下界始终是原始数组里count(k)，即res应初始化为cntK（暴力法/解法二）或依赖空子数组净收益为 0 的设定（解法三），不能只盯着"找到最佳子数组"而丢了基准情形。

5. 用错 Kadane 变体

经典 Kadane 要求最大和子数组至少包含一个元素；但本题中空子数组是合法的（不选任何子数组，净收益 0）。因此运行和变负时必须允许归零（cnt = max(cnt, 0)），表示"放弃前面这些元素，不把它们纳入操作子数组"，否则可能得到负收益，反而拉低答案。

六、三种解法对比与总结

本仓库另有一道同名函数maxFrequency的题目 python/1838-frequency-of-the-most-frequent-element.py，其解法为"排序 + 滑动窗口"（nums.sort()后维护窗口内"目标最大值 × 长度 − 窗口和 ≤ k"的不等式），虽然函数名相同，但问题是"最多执行 k 次 +1 操作使某个元素出现次数最多"，建模与本文的子数组整体加常数完全不同，可以对照学习以区分两类"频率最大化"问题。

一句话总结：把"选一个子数组整体加常数"翻译成"每个候选值对应的 +1（多出num）/ −1（损失k）映射序列的最大子数组和"，就完成了从暴力 $O(50n^2)$ 到 Kadane $O(50n)$ 再到哈希表单趟 $O(n)$ 的三级优化；全程记得空子数组合法、候选值间状态独立、答案下界为原始count(k)，即可一次性写对。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode