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

标签: 数组 模拟

难度: Easy

给你一个整数数组 nums ,如果 nums 至少 包含 2 个元素,你可以执行以下操作:

  • 选择 nums 中的前两个元素并将它们删除。

一次操作的 分数 是被删除元素的和。

在确保 所有操作分数相同 的前提下,请你求出 最多 能进行多少次操作。

请你返回按照上述要求 最多 可以进行的操作次数。

示例 1:

输入:nums = [3,2,1,4,5]
输出:2
解释:我们执行以下操作:
- 删除前两个元素,分数为 3 + 2 = 5 ,nums = [1,4,5] 。
- 删除前两个元素,分数为 1 + 4 = 5 ,nums = [5] 。
由于只剩下 1 个元素,我们无法继续进行任何操作。

示例 2:

输入:nums = [3,2,6,1,4]
输出:1
解释:我们执行以下操作:
- 删除前两个元素,分数为 3 + 2 = 5 ,nums = [6,1,4] 。
由于下一次操作的分数与前一次不相等,我们无法继续进行任何操作。

提示:

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 1000

Submission

运行时间: 16 ms

内存: 16.0 MB

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        res=0
        t=nums[0]+nums[1]
        for i in range(1,len(nums),2):
            if nums[i-1]+nums[i]==t:
                res+=1
            else:break
        return res

Explain

此题解的基本思路是首先计算数组 nums 的前两个元素的和作为目标分数 t。接着,它通过遍历数组,每次检查相邻的两个元素(以2为步长),比较这两个元素的和是否等于 t。如果是,增加结果计数 res;如果不是,立即停止遍历。这种方法假定数组中的元素顺序可以直接用来形成连续的操作,且一旦发现一对元素和不等于 t,就不再尝试找其他可能的配对。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        res = 0  # 初始化操作次数为0
        t = nums[0] + nums[1]  # 计算前两个元素的和作为目标分数
        for i in range(1, len(nums), 2):  # 从索引1开始,步长为2进行遍历
            if nums[i-1] + nums[i] == t:  # 检查当前和前一个元素的和是否等于目标分数
                res += 1  # 如果相等,增加操作次数
            else:
                break  # 如果不相等,停止遍历
        return res  # 返回操作次数

Explore

在题解中,算法从索引1开始遍历是因为它首先计算了索引0和索引1的和作为目标分数t。从索引1开始,步长为2,实际上是检查这对元素(索引0和1)以及之后每一对连续元素(2和3,4和5等)。这样,算法可以一次性检查所有连续的元素对是否符合目标分数t。

是的,这种方法会遗漏其他可能的有效配对。算法只检查了连续的元素对,如果某一对连续元素的和不等于t,算法就会停止。这会导致不考虑后续可能存在的有效配对。例如,在数组[1, 9, 5, 5]中,如果目标分数t为10,仅检查连续元素对会错过[1, 9]和[5, 5]这样的有效配对。

题解中确实只检查了连续的元素对,步长为2是为了确保每次检查都是连续的两个元素。这种方法没有考虑可能的非连续元素配对。如果目标是找出所有可能的有效配对,无论它们是否连续,那么需要采用不同的方法,例如使用哈希表来记录元素和其频率,然后匹配合适的元素对来满足相同的操作分数t。