Acwing 800.数组元素的目标和
题解
- 两个数组升序,
i
指针从a
数组头往后走,for
循环 j
指针从b
数组尾部往前走,while
循环,只要a[i] + b[j] > x
,j
就一直往前走,知道有可能等于x
为止- 这样
i
和j
最多都只会走n
步,故时间复杂度为O(n)
a = [0] * 100010
b = [0] * 100010
def main():
n, m, x = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
j = m - 1
for i in range(n):
while (a[i] + b[j] > x) and (j > 0):
j -= 1
if a[i] + b[j] == x:
print(i, j)
main()