第2题-互补数组

会员专享

请先登录，开通会员或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

题目思路

考虑使用map维护a[i] + b[i]相等的数量cnt，对于每一种互补的所有下标，其可以产生的对应的子序列数量等于 $2^{cnt} -1$ 种，即排除一个元素都不选的剩余情况。

时间复杂度O(nlogn)

Java

小红定义两个数组是互补的，当且仅当数组每一个位置的数字之和都相同。

小红有两个长度为 $n$ 的数组，分别是a和b，她想知道有多少个子序列对应的数组是互补的。