双指针的核心:将上一状态指针所表达的信息传递至下一状态,从而减少无谓的搜索。
对于任意A[i]+B[j]>X, A,B单调递增,则显然,A[i+1]+B[j]>A[i]+B[j]>X。因此,指针j应该向j-1方向搜索,反之亦然。
因此对于任意的指针i,对应的指针j搜索的区域在A[i]+B[j]>X与A[i]+B[j]<X之间,搜索的个数是常数的,因此总的时间复杂度为O(n)。
N, M, X = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
i = 0
j = 0
for i in range(N):
while A[i] + B[j] > X:
j -= 1
while A[i] + B[j] < X and j < len(B) - 1:
j += 1
if A[i] + B[j] == X:
break
print(i, j)
厉害,一下子就听懂了