Working 2sum solver

Question

This is my first working 2sum solver. It works by finding the difference for our target in s to determine if that 2sum exists.

Suppose our target is -5. I start with the first index in s and use subtraction, (-5-(-8) = 3), and the result is 3. The code will check the difference in s. If the difference exists in the list s then the output is yes.

s = [-8,3,5,1,3]
target = -5

for j in range(0, len(s)):
  if target-int(s[j]) in s[j+1:len(s)]:
   print('yes')
   quit()

print('no')

I fixed a bug where a false yes was returned when int(s[j]) was equal to target-int(s[j]). I did this by s[j+1:len(s)] An example would be our target would be 4, but our input for s was [2]. It would say yes because int(s[j]) was equal to target-int(s[j]).

Is it possible to write this code all in one or two lines of code?

Answer 1

Translating your code directly into a one-liner:

s = [-8,3,5,1,3]
target = -5

is_2sum = any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))
print(is_2sum)

A few notes:

• The loop is now translated into a generator expression: we record whether every difference is present in the remainder of the list and combine this with any, which will check if the resulting list contains a True.

• In particular, note that we do not construct a list by list comprehension inside the call to any. Indeed, by using a generator expression we allow for an early exit as soon as a True value is found, potentially speeding up quite a bit the execution on positive instances.

• Your approach runs in quadratic time. However, this algorithm can be further optimized to run in linear time (see e.g., a similar question on CS.SE).

If you are fine with a quadratic time algorithm, another alternative is to brute-force every pair. It is straightforward to generalize such an algorithm to k-sum as well. So just for fun, we might also do:

from itertools import combinations 

s = [-8,3,5,1,3]
target = -5

is_2sum = any(sum(p) == target for p in combinations(s, 2))
print(is_2sum)

As stated, this is not highly scalable, but it should very easy for a beginner to read and to understand (if that matters).

Answer 2

• You should make this a function.
• You should use 4 spaces for indentation.
• If s becomes a count of numbers in a dictionary, then in becomes performs in \$O(1)\$ time, where lists perform in \$O(n)\$ time.
• Using quit isn't really idiomatic, and was added to make exiting the REPL easier.
• Rather than for j in range(0, len(s)) you can use for item in s.
• Use better variable names, s and j are just meh.
• You can use a comprehension, with any to reduce noise.

import collections


def has_two_sum(items, target):
    items = collections.Counter(map(int, items))
    for item in map(int, items):
        remainder = target - item
        if items.get(remainder, 0) >= (2 if item == remainder else 1):
            return True
    return False


if has_two_sum(s, target):
    print('yes')
else:
    print('no')

Or you can write it in on of these one liners, which look like garbage:

s=collections.Counter(map(int,s));print(['no','yes'][any(map(lambda i:s.get(t-i,0)>=1+(i==t-i),s))])
f=set();print(['no','yes'][any(map(lambda i:(t-i in f,f.add(i))[0],s))])

Answer 3

I believe this will solve your problem:

# Using ternary operator to condense the print's
two_sum = lambda s, target: print('yes') if any(map(lambda x: target-x in s and s.count(x)>1, s)) else print('no')

# If s.count(x) is 1, it means the subtraction resulted in the same element took that time for the operation, which we don't want to happen. So the count must be greater then 1

two_sum([-8, 3, 5, 1, 3], -5)
# Output is "yes"

two_sum([2], 4)
# Output is "no"

So, we wrapped the function in a lambda, used another lambda in the map call and preserved all items in the list, checking if the output matches another element besides the one took in for the calculation.

Benchmark

I was wondering if @Juho's answer provided a faster function, so I benchmarked both.

So:

two_sum = lambda s, target: any(map(lambda x: target-x in s and s.count(x)>1, s))

is_2sum = lambda s, target: any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))

# The print's aren't necessary for the benchmark.

Then, I ran both at Google Colab with the following code:

two_sum = lambda s, target: any(map(lambda x: target-x in s and s.count(x)>1, s))

is_2sum = lambda s, target: any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))

test_function = two_sum
# test_function = is_2sum

if __name__ == "__main__":
    import timeit
    setup = "from __main__ import test_function"
    average=0
    for i in range(0,100):
      average=average+timeit.timeit("test_function([-8, 3, 1, 5, 1, 3], -5)", setup=setup, number=1000000)
    print(average/100)

The method timeit.timeit() will run each function 1.000.000 times, then I record the outputs of 100 iterations (so, we actually ran the function 100.000.000 times) and take the average.

Results:

For the function two_sum:
First run: 0.9409843384699957
Second run: 0.948360692339993

For the function is_2sum:
First run: 0.9963176720300112
Second run: 0.998327726480004

As you can see, there is an increase in performance for two_sum function, whether this comes from the use of map() and avoiding lists operations, I don't know, but it's a bit faster.