难度: Medium
Submission
运行时间: 83 ms
内存: 27.6 MB
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
i, j = 0, len(nums)-1
pre, suf = nums[0], nums[-1]
ret = 0
while i < j:
if pre < suf:
i += 1
pre += nums[i]
ret += 1
elif pre > suf:
j -= 1
suf += nums[j]
ret += 1
else:
i += 1
j -= 1
pre = nums[i]
suf = nums[j]
return ret
Explain
此题解采用双指针方法来寻找最少的合并次数，使得数组变成回文序列。算法从数组的两端开始，使用两个指针i和j分别指向数组的首尾，同时用pre和suf记录从两端开始累加的数值。当两指针相遇前，比较pre和suf的值：如果pre小于suf，说明需要增加左边的数值，因此将左指针向右移动，并累加到pre上，同时增加操作计数；如果pre大于suf，则右指针向左移动，并累加到suf上，同样增加操作计数。如果pre和suf相等，两指针同时向中间移动，并更新pre和suf为新的指针所指的数值。这个过程持续进行直到两指针相遇，操作数即为最少的合并次数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
i, j = 0, len(nums)-1 # 初始化左右指针
pre, suf = nums[0], nums[-1] # 初始化左右累计和
ret = 0 # 初始化操作次数计数
while i < j: # 当左指针小于右指针时循环
if pre < suf: # 如果左边累计和小于右边
i += 1 # 移动左指针
pre += nums[i] # 累加左边的值到左边累计和
ret += 1 # 增加操作次数
elif pre > suf: # 如果左边累计和大于右边
j -= 1 # 移动右指针
suf += nums[j] # 累加右边的值到右边累计和
ret += 1 # 增加操作次数
else: # 如果左右累计和相等
i += 1 # 移动左指针
j -= 1 # 移动右指针
pre = nums[i] # 更新左边累计和为新左指针的值
suf = nums[j] # 更新右边累计和为新右指针的值
return ret # 返回总的操作次数
Explore
当两个累计和相等时，意味着从数组的两端到当前指针位置可以形成一个局部的回文结构。同时移动两个指针并更新累计和是为了尝试扩展这个局部回文结构。这种做法通常是有效的，因为任何单边的操作都会破坏当前的平衡，增加不必要的合并次数。然而，这种方法在特定的数组排列下可能不是最优，例如两端累积和相等但中间部分需要多次操作才能平衡。在这种情况下，可能存在特殊的策略通过调整操作顺序来减少操作次数。
当左右指针的累计和不等时，增加操作计数是为了尝试通过合并较小的累计和来达到与另一侧相等，从而逐步构建回文结构。这种操作逻辑基于寻找最少的操作次数来平衡两端的累计和。虽然此策略是直观的，但在特定情况下，例如连续多个小值可以通过一次合并达到较大值，可能存在通过不同的合并顺序来减少总的合并次数的可能。
如果数组中存在负数或零，基本的算法逻辑不需要调整，因为算法依赖于累计和的比较，而不是具体的值。然而，负数的存在可能导致累计和减少，这可能使得达到平衡更为复杂，需要更多的操作来抵消负数的影响。零的存在通常不会影响累计和，但在计算操作次数时需要考虑，因为它不会改变累计和的值。
在双指针法的实现中，每次移动指针后，累计和的更新通过直接将移动后的指针所指的数组元素值加到当前的累计和上来确保其正确性。这种更新方式确保了无论指针如何移动，累计和总是反映了从数组端点到当前指针的所有元素的总和。这是一种简单且有效的方法来维护和更新累计和，确保算法的准确性。