如何优化大规模输入下的子数组转换问题解法？

问题本质分析 #

原问题要求选择一个连续子数组并添加同一个整数z，最大化目标值k的出现次数。核心观察：

• 操作后，子数组外的k保持不变。
• 选择z=k-v时，子数组中所有等于v的元素会变成k，而子数组中的k会变成v（不再是k）。
• 对于每个非k的值v，我们需要找到连续子数组S，使得(S中v的数量 - S中k的数量)最大，这个值加上原数组中k的总数就是操作后的最大k数量。

关键优化：全局偏移量 #

直接维护每个v的前缀和会导致时间复杂度过高，我们引入全局偏移量offset来统一处理k对所有v的影响：

• 每遇到一个k，offset加1（等价于所有v的前缀和减1）。
• 对于每个v，实际前缀和 = 该v的当前前缀计数 - offset。

算法步骤 #

1. 统计原数组中k的总数量totalK。
2. 初始化：
   • offset：记录遇到的k的数量，初始为0。
   • currentPrefix哈希表：存储每个非k值v的当前前缀计数（仅统计v出现的次数）。
   • minPrefix哈希表：存储每个v对应的最小实际前缀和（用于计算最大子数组和）。
   • maxGain：记录所有v对应的最大(v数量 - k数量)值，初始为0。
3. 遍历数组：
   • 若当前元素是k，直接增加offset。
   • 若当前元素是v≠k：
     • 若v未在哈希表中，初始化其前缀计数为0，并设置初始最小前缀和为0 - offset（对应遍历前的前缀和）。
     • 增加v的前缀计数。
     • 计算当前实际前缀和：currentSum = currentPrefix[v] - offset。
     • 计算当前v对应的最大增益：gain = currentSum - minPrefix[v]，更新maxGain。
     • 若当前实际前缀和小于minPrefix[v]，更新minPrefix[v]。
4. 最终答案为totalK + max(maxGain, 0)（若maxGain为负，说明操作无收益，选择不执行操作）。

Java代码实现 #

import java.util.HashMap;
import java.util.Map;

public class MaxKFrequency {
    public int maxFrequency(int[] nums, int k) {
        int totalK = 0;
        for (int num : nums) {
            if (num == k) {
                totalK++;
            }
        }
        
        int offset = 0;
        Map<Integer, Integer> currentPrefix = new HashMap<>();
        Map<Integer, Integer> minPrefix = new HashMap<>();
        int maxGain = 0;
        
        for (int num : nums) {
            if (num == k) {
                offset++;
            } else {
                currentPrefix.putIfAbsent(num, 0);
                if (!minPrefix.containsKey(num)) {
                    minPrefix.put(num, 0 - offset);
                }
                
                currentPrefix.put(num, currentPrefix.get(num) + 1);
                int currentSum = currentPrefix.get(num) - offset;
                int gain = currentSum - minPrefix.get(num);
                
                if (gain > maxGain) {
                    maxGain = gain;
                }
                
                if (currentSum < minPrefix.get(num)) {
                    minPrefix.put(num, currentSum);
                }
            }
        }
        
        return totalK + Math.max(maxGain, 0);
    }
    
    public static void main(String[] args) {
        MaxKFrequency solution = new MaxKFrequency();
        // 示例1
        int[] nums1 = {2,3,2,4,3,2};
        System.out.println(solution.maxFrequency(nums1, 2)); // 输出4
        // 示例2
        int[] nums2 = {6,4,4,5,4,4};
        System.out.println(solution.maxFrequency(nums2, 6)); // 输出5
        // 示例3
        int[] nums3 = {2,5,2,5,2};
        System.out.println(solution.maxFrequency(nums3, 2)); // 输出4
    }
}

复杂度分析 #

• 时间复杂度：O(n)，每个元素仅遍历一次，哈希表操作平均为O(1)。
• 空间复杂度：O(m)，m为数组中非k的不同元素数量，最坏情况为O(n)（所有元素都不等于k），符合2e5规模的内存要求。

内容的提问来源于stack exchange，提问作者CodeCrusader