I have an input list

lst = [2, 4, 3, 6, 5]

If I say target = 7, I would like to get

[(0, 4), (1, 2)]

These are the indices of the pairs of numbers in lst which add up to target (7).

How we can obtain the expected result using a single for loop?

CodePudding user response：

Think about it this way: for every number n at index i you encounter, you need to find an index j that contains 7 - n. You can do this in a single pass over the list by maintaining the following structures:

• A list of the pairs you've found so far
• A map of 7 - n: i, so that when you encounter 7 - n at index j, you can add the pair i, j

A simple approach using just one loop would be

from collections import defaultdict

def find_target(data, target):
    pairs = []
    found = defaultdict(list)
    for i, n in enumerate(data):
        m = target - n
        found[m].append(i)
        if n in found:
            pairs.extend((j, i) for j in found[n])
    return pairs

Using defaultdict to hold a list of indices for all the possible duplicates is a simple way to ensure that you get all the possible combinations.

For your specific case:

>>> find_target([2, 4, 3, 6, 5], 7)
[(1, 2), (0, 4)]

The result is sorted by the second index (since that determines when a pair enters the list). If you want to sort it by the first index, you can do so:

>>> result = find_target([2, 4, 3, 6, 5], 7)
>>> result.sort()
>>> result
[(0, 4), (1, 2)]

Or more wastefully,

>>> sorted(find_target([2, 4, 3, 6, 5], 7))
[(0, 4), (1, 2)]

CodePudding user response：

In a single list-comprehension: filter by target-value and skip duplicate values.

target = 7
lst = [2, 4, 3, 6, 5]

output = [(i1, i2) for i1, j1 in enumerate(lst) for i2, j2 in enumerate(lst) if j1 j2 == target and i1 < i2]
print(output)

or, to avoid the and, using a slice (together with a shift of the i2-index):

[(i1, i2) for i1, j1 in enumerate(lst) for i2, j2 in enumerate(lst[i1:], start=i1) if j1 j2 == target]