Ваш код выполняется за O(n^2). То, что вложенный цикл начинается с i + 1, на оценку не влияет.

Решение за O(n):

val_to_pos = {x: i for i, x in enumerate(arr)}
for i, x in enumerate(arr):
    pair = target - x
    pair_pos = val_to_pos.get(pair)
    if pair_pos == i and must_be_distinct:
        continue
    if pair_pos is not None:
        return (x, pair)
return None