3 sum implementation in python 2.7 Working on below problem, looking for advice on code style, functional bug and time complexity improvements.

Also looking for advice in,


If array is not sorted, any solutions available for O(n^2) time complexity?
In my loop, I always search from exclude_index + 1 to reduce duplicate, is it a safe start boundary?


Problem,

Given a sorted array and a target number, tell whether there are three numbers in the array which add up to the target number. (Time complexity should be O(n^2)) 

Source code,

def two_sum(numbers, start, end, target, exclude_index):
    while start &lt; end:
        if start == exclude_index:
            start += 1
        elif end == exclude_index:
            end -= 1
        elif numbers[start] + numbers[end] &gt; target:
            end -= 1
        elif numbers[start] + numbers[end] == target:
            print numbers[start], numbers[end], numbers[exclude_index]
            start += 1
            end -= 1
            while start &lt; end and (numbers[start] == numbers[start - 1] or start == exclude_index):
                start += 1
            while start &lt; end and (numbers[end] == numbers[end + 1] or end == exclude_index):
                end -= 1
        else:
            start += 1
def three_sum(numbers, target):
    for exclude_index in range(len(numbers)):
        if exclude_index &gt; 0 and numbers[exclude_index] == numbers[exclude_index - 1]:
            continue
        two_sum(numbers, exclude_index + 1, len(numbers) - 1, target - numbers[exclude_index], exclude_index)

if __name__ == "__main__":
    numbers = [1, 3, 4, 6, 7, 8, 9, 9, 10, 12]
    three_sum(numbers, 15)
As with most of your questions, your code violates PEP8.




Don't print your output.
Since \$\text{start} = \text{exclude_index} + 1\$ you can never visit exclude_index.


Your code with the above changes make your code more readable.
But it'd be better if you:


Start using Python's standard library. Itertools can drastically improve your codes readability.
Stop relying on while so much.
Use a dictionary, it's fast, and increases readability.
sorted runs in \$O(n\log(n))\$ time.


Using itertools.combinations_with_replacement and collections.Counter you can generate all three of your numbers, still in \$O(n^2)\$ time.


Pass a sorted list to combinations_with_replacement, and generate two numbers.
Check target - i - j is in the list of numbers, and that it is greater or equal to i and j.
Group; i, j and k, in a Counter and check there is enough of each number in the original list.




import collections
import itertools

def three_sum(numbers, target):
    Counter = collections.Counter
    count = Counter(numbers)
    for i, j in itertools.combinations_with_replacement(list(sorted(count)), 2):
        k = target - i - j
        if k in count and j &lt;= k &gt;= i:
            nums = (i, j, k)
            if all(count[k] &gt;= v for k, v in Counter(nums).items()):
                yield nums