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

解决leetcode第3943题递增后的数对数量

news 2026/5/26 2:50:53

3943.递增后的数对数量

难度：困难

问题描述：

给你两个整数数组nums1和nums2，以及一个二维整数数组queries。

每个queries[i]都属于以下两种类型之一：

[1,x,y,val]：将nums2[x..y]中的每个元素都增加val。

[2,tot]：计算满足nums1[j]+nums2[k]==tot的数对(j,k)的数量。

返回一个整数数组answer，其中answer[j]表示第j个类型2查询的数对数量。

示例1：

输入：nums1=[1,2],nums2=[3,4],queries=[[2,5],[1,0,0,2],[2,5]]

输出：[2,1]

解释：

queries[0]=[2,5]：有效数对为nums1[0]+nums2[1]=1+4=5和nums1[1]+nums2[0]=2+3=5。

queries[1]=[1,0,0,2]：将nums2[0]增加2，得到nums2=[5,4]。

queries[2]=[2,5]：有效数对为nums1[0]+nums2[1]=1+4=5。

因此，answer=[2,1]。

示例2：

输入：nums1=[1,1],nums2=[2,2,3],queries=[[2,4],[1,0,1,1],[2,4]]

输出：[2,6]

解释：

queries[0]=[2,4]：有效数对为nums1[0]+nums2[2]=1+3和nums1[1]+nums2[2]=1+3。

queries[1]=[1,0,1,1]：将nums2[0]和nums2[1]各增加1，得到nums2=[3,3,3]。

queries[2]=[2,4]：nums1=[1,1]中的每个元素都可以与nums2=[3,3,3]中的每个元素配对，因为1+3=4，总共有2×3=6个数对。

因此，answer=[2,6]。

示例3：

输入：nums1=[2,5,8,4],nums2=[1,3,8],queries=[[2,9],[1,1,2,1],[2,10]]

输出：[1,0]

解释：

queries[0]=[2,9]：唯一有效数对为nums1[2]+nums2[0]=8+1=9。

queries[1]=[1,1,2,1]：将nums2[1]和nums2[2]各增加1，得到nums2=[1,4,9]。

queries[2]=[2,10]：没有数对的和为10。

因此，answer=[1,0]。

提示：

1<=nums1.length<=5

1<=nums2.length<=5*10**4

1<=nums1[i],nums2[i]<=10**5

1<=queries.length<=5*10**4

queries[i].length==2 or 4

queries[i]==[1,x,y,val]，或

queries[i]==[2,tot]

0<=x<=y<nums2.length

1<=val<=10**5

1<=tot<=10**9

问题分析：

对于本题来说，从查询序列中取出每一个查询，按要求进行处理即可。对于第一种类型的查询[1,x,y,val]，将nums2[x..y]中的每个元素都增加val，这通过函数increase_the_value_of_each_element_within_the_specified_range_by_val(num2,querie)实现，对于第二种类型的查询[2,tot]，计算满足nums1[j]+nums2[k]==tot的数对(j,k)的数量，这通过函数get_ordered_pair_that_meets_the_conditions(num1,num2,tot)实现，在主程序中，只需要依次对查询序列queries中的每个查询，调用相应的处理函数进行处理，最后将数对数量的列表输出即解决了问题。

程序如下：

#计算满足 nums1[j] + nums2[k] == tot 的数对 (j, k)的数量并返回 def get_ordered_pair_that_meets_the_conditions(num1,num2,tot): m=len(num1) n=len(num2) a=[] for i in range(m): for j in range(n): if num1[i]+num2[j]==tot: a.append([i,j]) return len(a) #将nums2[x..y] 中的每个元素都增加val def increase_the_value_of_each_element_within_the_specified_range_by_val(num2,querie): n=len(num2) x=querie[1] y=querie[2] val=querie[3] for i in range(x,y+1): num2[i]=num2[i]+val return num2 #主程序 num1=eval(input("enter the first num1=")) num2=eval(input("enter the second num2=")) queries=eval(input("enter the second queries=")) a=[] for i in queries: b=i[0] if b==1: num2=increase_the_value_of_each_element_within_the_specified_range_by_val(num2,i) else: c=get_ordered_pair_that_meets_the_conditions(num1,num2,i[1]) a.append(c) print(a)