当前位置：首页 > article >正文

LeetCode 3038 相同分数的最大操作数目I

article 2025/3/29 3:02:56

【算法题解】在数组中进行等和操作的最大次数

问题描述

给定一个整数数组 nums，每次操作选择前两个元素删除，分数为两数之和。要求所有操作的分数相同，求最多能进行多少次操作。

示例 1
输入：nums = [1,5,3,3,4,1,3,2,2,3]
输出：2（正确操作：(1+5)=6，(3+3)=6，共 2 次）

示例 2
输入：nums = [3,2,1,4,5]
输出：2（正确操作：(3+2)=5，(1+4)=5，共 2 次）

核心思路分析

错误思路回顾

固定前两数之和（初始错误）：
直接使用前两个元素的和作为目标和，忽略其他可能的组合。
❌ 错误原因：未枚举所有可能的和，例如示例 2 中前两数和为 5，后续组合 1+4=5 也满足条件。
顺序匹配元素（中间错误）：
仅检查相邻元素对是否满足和，未考虑非相邻元素的组合。
❌ 错误原因：操作不要求元素连续，只需每次选两个未使用的元素。

正确思路：枚举所有可能的和 + 双指针法

枚举所有可能的两数之和：
遍历数组中所有两两组合，得到可能的目标和 target。
排序数组 + 双指针法：
对数组排序后，使用双指针（左指针从头、右指针从尾）寻找和为 target 的元素对：
- 若和等于 target：计数 +1，移动左右指针。
- 若和小于 target：左指针右移（增大和）。
- 若和大于 target：右指针左移（减小和）。
取最大值：
对每个 target 计算可形成的操作次数，取最大值。

解决方案代码

import java.util.Arrays;

class Solution {
    public int maxOperations(int[] nums) {
        int n = nums.length;
        if (n < 2) return 0; // 边界条件
        
        int maxOps = 0;
        // 枚举所有可能的两数之和作为目标和
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int target = nums[i] + nums[j];
                int[] temp = nums.clone(); // 复制数组避免修改原数组
                Arrays.sort(temp); // 排序后使用双指针
                
                int left = 0, right = n - 1, ops = 0;
                while (left < right) {
                    int sum = temp[left] + temp[right];
                    if (sum == target) { // 找到有效对
                        ops++;
                        left++;
                        right--;
                    } else if (sum < target) { // 增大和
                        left++;
                    } else { // 减小和
                        right--;
                    }
                }
                maxOps = Math.max(maxOps, ops); // 更新最大值
            }
        }
        return maxOps;
    }
}

代码关键点解析

枚举目标和：
使用两层循环遍历所有两两组合（共 O (n²) 种可能），确保覆盖所有可能的操作分数。
排序与双指针：
- 排序后，双指针法可在 O (n) 时间内找到所有和为 target 的元素对。
- 指针移动策略：左指针找较小值，右指针找较大值，确保每次匹配最优。
避免重复计算：
使用数组副本 temp 进行排序，避免修改原数组影响后续枚举。

复杂度分析

时间复杂度：O(n³)
- 枚举所有两两组合：O (n²)。
- 每次双指针操作：O (n)。
- 总复杂度：O (n² × n) = O (n³)。
空间复杂度：O(n)
- 存储数组副本 temp：O(n)。

测试用例验证

示例 1：`[1,5,3,3,4,1,3,2,2,3]`

枚举所有和，找到 target=6（如 1+5 或 3+3）。
排序后数组：[1,1,2,2,3,3,3,3,4,5]。
双指针匹配：(1+5), (1+5) → 无效（和为 6 的对为 (1+5), (3+3), (3+3), (2+4)，共 4 对？但实际有效操作是每次选两个未使用的元素，需确保每对不重叠）。
✅ 正确输出：2（实际有效操作：(1+5), (3+3)，共 2 次，因为后续元素无法再组成不重叠的对）。