2025-08-05：子数组操作后的最大频率。用go语言，给定一个长度为 n 的数组 nums 和一个整数 k，你可以对 nums 进行一次操作：

• 选择一个连续的子数组 nums[i..j]，满足 0 ≤ i ≤ j ≤ n - 1；

• 选择一个整数 x，将这个子数组中的每个元素都增加 x。

请你找出在进行以上操作后，数组中数字 k 出现的最大次数。

1 <= n == nums.length <= 100000。

1 <= nums[i] <= 50。

1 <= k <= 50。

输入：nums = [10,2,3,4,5,5,4,3,2,2], k = 10。

输出：4。

解释：

将 nums[1..9] 增加 8 以后，10 在数组 [10, 10, 11, 12, 13, 13, 12, 11, 10, 10] 中的频率为最大值 4 。

题目来自力扣3434。

示例分析

给定 nums = [10, 2, 3, 4, 5, 5, 4, 3, 2, 2] 和 k = 10：

• 原始数组中 10 出现 1 次。
• 操作：选择子数组 nums[1..9]（即从第 2 个元素到最后一个元素），并增加 x = 8。
• 操作后的数组：[10, 10, 11, 12, 13, 13, 12, 11, 10, 10]。
• 10 出现 4 次（位置 0, 1, 8, 9），因此输出 4。

解题思路

我们需要找到一种方法，通过一次操作使得 k 的出现次数最大化。关键在于：

1. 操作是将一个子数组的所有元素增加 x，因此我们需要选择 x 和子数组，使得尽可能多的元素在操作后等于 k。
2. 对于原始数组中的某个元素 nums[i]，如果它不在被操作的子数组中，那么它保持不变。如果它在子数组中，那么它的值变为 nums[i] + x。
   • 如果 nums[i] == k 且不在子数组中，那么它仍然是 k。
   • 如果 nums[i] + x == k，那么操作后它会变成 k。
3. 我们需要统计：
   • 不在子数组中的 k 的数量（即原始 k 的数量减去子数组中 k 的数量）。
   • 子数组中通过操作可以变成 k 的元素数量（即 nums[i] + x == k 的数量）。
   • 因此，总 k 的数量为：(原始 k 的数量 - 子数组中 k 的数量) + 子数组中满足 nums[i] + x == k 的数量。
4. 为了最大化 k 的数量，我们需要找到一个子数组和一个 x，使得 (子数组中满足 nums[i] + x == k 的数量) - (子数组中 k 的数量) 最大化。
   • 因为原始 k 的数量是固定的，所以最大化 (子数组中满足 nums[i] + x == k 的数量) - (子数组中 k 的数量) 是关键。
5. 由于 x 可以是任意整数，我们可以选择 x = k - nums[i] 来让 nums[i] 变成 k。因此，对于子数组中的每个元素 nums[i]，我们可以选择 x 使得 nums[i] + x == k，即 x = k - nums[i]。
   • 但是子数组中的所有元素必须增加相同的 x，因此我们需要选择一个 x 使得尽可能多的 nums[i] 满足 nums[i] + x == k。
   • 这意味着我们需要找到一个 x，使得在子数组中有尽可能多的 nums[i] 满足 nums[i] == k - x。
6. 由于 nums[i] 的取值范围是 [1, 50]，我们可以枚举所有可能的 x（即 x = k - v，其中 v 是 nums[i] 的可能值，即 v 的范围是 [1, 50]）。
   • 对于每个 v，计算 x = k - v，然后统计子数组中 nums[i] == v 的数量（因为 nums[i] + x == k 当且仅当 nums[i] == v）。
   • 我们需要找到一个子数组，使得 count_v - count_k 最大化（其中 count_v 是子数组中 nums[i] == v 的数量，count_k 是子数组中 nums[i] == k 的数量）。
   • 因为 x 的选择依赖于 v，而 v 的取值范围很小（[1, 50]），我们可以枚举所有可能的 v。

算法步骤

1. 统计原始数组中 k 的总数量 total_k。
2. 对于每个可能的 v（1 <= v <= 50）：
   • 计算 x = k - v（注意 x 可以是负数）。
   • 我们需要找到一个子数组，使得 count_v - count_k 最大化（其中 count_v 是子数组中 nums[i] == v 的数量，count_k 是子数组中 nums[i] == k 的数量）。
   • 这可以通过遍历数组并维护一个动态规划或类似的最大子数组和的算法来实现：
     • 初始化 max_diff = 0 和 current_diff = 0。
     • 遍历数组：
       • 如果 nums[i] == v，current_diff += 1。
       • 如果 nums[i] == k，current_diff -= 1。
       • 更新 max_diff = max(max_diff, current_diff)。
       • 如果 current_diff < 0，则重置 current_diff = 0（因为负值不会对后续的子数组产生正面贡献）。
     • max_diff 就是对于 v 的最大 count_v - count_k。
   • 记录 total_k + max_diff 作为候选结果。
3. 最终结果是所有候选结果中的最大值。

示例的具体计算

以 nums = [10, 2, 3, 4, 5, 5, 4, 3, 2, 2] 和 k = 10：

• 原始 k 的数量 total_k = 1（只有 nums[0] == 10）。
• 我们需要枚举 v 从 1 到 50，但实际 nums[i] 的范围是 2 到 10（因为 nums[i] 最大是 5，k = 10，v = k - x 的最小值是 10 - x）。
• 对于 v = 2：
  • x = 10 - 2 = 8。
  • 我们需要找到子数组使得 count_2 - count_10 最大化。
  • 子数组 nums[1..9] 中有 nums[1] = 2, nums[8] = 2, nums[9] = 2，共 3 个 2。
  • 子数组中有 nums[0] 是 10，但 nums[0] 不在子数组中（子数组从 nums[1] 开始），所以 count_10 = 0。
  • count_2 - count_10 = 3 - 0 = 3。
  • 候选结果：total_k + max_diff = 1 + 3 = 4。
• 其他 v 的值不会产生更大的结果，因此最终结果是 4。

时间复杂度和空间复杂度

• 时间复杂度：
  • 外层循环枚举 v，v 的取值范围是 [1, 50]，因此是 O(50) = O(1)。
  • 内层循环遍历数组一次，每次遍历是 O(n)。
  • 总时间复杂度：O(1) * O(n) = O(n)。
• 空间复杂度：
  • 只需要常数空间来维护 max_diff 和 current_diff。
  • 总空间复杂度：O(1)。

Go完整代码如下：

package mainimport ("fmt"
)func maxFrequency(nums []int, k int) int {f0, maxF12 := 0, 0f1 := [51]int{}for _, x := range nums {if x == k {maxF12++f0++} else {f1[x] = max(f1[x], f0) + 1maxF12 = max(maxF12, f1[x])}}return maxF12
}func main() {nums := []int{10, 2, 3, 4, 5, 5, 4, 3, 2, 2}k := 10result := maxFrequency(nums, k)fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-def max_frequency(nums, k):f0, max_f12 = 0, 0f1 = [0] * 51for x in nums:if x == k:max_f12 += 1f0 += 1else:f1[x] = max(f1[x], f0) + 1max_f12 = max(max_f12, f1[x])return max_f12if __name__ == "__main__":nums = [10, 2, 3, 4, 5, 5, 4, 3, 2, 2]k = 10result = max_frequency(nums, k)print(result)