难度: Medium
Submission
运行时间: 155 ms
内存: 35.9 MB
class Solution:
def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:
if sum(nums1) == sum(nums2):
return len(nums1)
nums = []
for x,y in zip(nums1,nums2):
nums.append(x-y)
d = {0:-1}
rv = 0
t = 0
for i in range(len(nums)):
t += nums[i]
if t in d:
v = i-d[t]
rv = max(rv,v)
if t not in d:
d[t] = i
return rv
Explain
这个题解的思路是先判断两个数组的元素和是否相等，如果相等直接返回数组长度。否则，将两个数组对应位置的元素相减，得到一个差值数组 nums。然后用哈希表存储差值数组的前缀和，键为前缀和，值为对应的索引。遍历差值数组，用当前索引减去哈希表中前缀和对应的索引，更新结果 rv。如果当前前缀和不在哈希表中，就将其加入哈希表。最后返回 rv 即可。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:
# 如果两个数组的元素和相等，直接返回数组长度
if sum(nums1) == sum(nums2):
return len(nums1)
# 创建差值数组 nums
nums = []
for x, y in zip(nums1, nums2):
nums.append(x - y)
# 初始化哈希表，键为前缀和，值为对应的索引
d = {0: -1}
rv = 0
t = 0
# 遍历差值数组
for i in range(len(nums)):
t += nums[i]
# 如果当前前缀和在哈希表中，更新结果 rv
if t in d:
v = i - d[t]
rv = max(rv, v)
# 如果当前前缀和不在哈希表中，将其加入哈希表
if t not in d:
d[t] = i
# 返回最终结果 rv
return rv
Explore
当两个数组的元素和相等时，表示从第一个元素到最后一个元素这整个区间内，两个数组的元素之和是相等的。因此，这是最大可能的索引范围（0到数组长度减1），并且这个区间的宽度就是整个数组的长度。在这种情况下，没有必要进行进一步的计算，因为已经达到了最大可能的宽度。
通过计算 `x - y` 来创建差值数组是有效的，因为此题的核心在于比较两个数组在任何子区间内元素的累积和是否相等。差值数组将两数组的对应值的差值进行累加，如果在某个区间的累加结果为0，就意味着这两个数组在这个区间内的元素和是相等的。这种方法不会导致信息丢失，因为我们关注的是区间和的相等性，而不是具体的值。
哈希表中使用前缀和作为键，索引作为值的设计是为了快速检查之前是否有相同的前缀和出现。如果在某个索引 `i` 处的前缀和已经在哈希表中存在，说明从哈希表中对应的索引+1到当前索引 `i` 的区间内，差值数组的元素和为0，即这个区间内 `nums1` 和 `nums2` 的元素和相等。通过用当前索引减去哈希表中前缀和对应的最早索引，我们可以找到一个宽度的范围，维护这个宽度的最大值即可得到答案。这种设计直接关联了前缀和与其索引，使得查找有效区间非常高效。
在遇到相同前缀和时，保留第一次出现该前缀和的索引而不更新是为了最大化区间的宽度。因为我们的目标是找到宽度最大的索引对，即两个索引之间的距离尽可能大。更新哈希表中的索引将导致后续计算的区间宽度变小，因为后面的索引与当前索引的距离肯定比最早的索引小。因此，保留最初出现的索引可以确保我们总是计算可能的最大宽度。