摘要
Title: 800. 数组元素的目标和
Tag: 双指针、二分
Memory Limit: 64 MB
Time Limit: 1000 ms

800. 数组元素的目标和

题意

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
思路
- 二分的思路比较好想
- 双指针的做法是：对于每个i都在B里找到一个j，使得a[i] + b[j] >= x，并且j是最靠左的一个

代码

二分 $O(nlogm)$

'''
Author: NEFU AB-IN
Date: 2022-01-25 18:45:48
FilePath: \ACM\Acwing\800.1.py
LastEditTime: 2022-01-25 19:05:39
'''
from bisect import bisect_left

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    for i in range(n):
        j = bisect_left(B, x - A[i])
        if j == m:
            continue
        if A[i] + B[j] == x:
            print(i, j)
            exit(0)

双指针 $O(n * m)$

'''
Author: NEFU AB-IN
Date: 2022-01-25 18:25:39
FilePath: \ACM\Acwing\800.py
LastEditTime: 2022-01-25 19:13:21
'''
if __name__ == "__main__":
    n, m, x = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    # 对于每个i都在B里找到一个j，使得a[i] + b[j] >= x，并且j是最靠左的一个
    # 所以就有了单调性，i往右走，j往左走

    j = m - 1
    for i in range(n):
        while j >= 0 and A[i] + B[j] > x:
            j -= 1
        if A[i] + B[j] == x:
            print(i, j)
            exit(0)

800. 数组元素的目标和

题意

思路

代码