Code Style
Your code contains a few lines that accomplish nothing and obfuscate your intent:
else: continue
If the conditional is false, you'll automatically
continue
on the next iteration without having to tell the program to do that.return None
All Python functions implicitly
return None
; however, PEP 8 recommends this practice.num_lst = list(range(len(nums)))
effectively generates a list of all the indices in thenums
input list. Then, you immediatelyenumerate
this list, which produces pairs of identical indicesindx, num
. If all you're attempting to do is iterate, this is significant obfuscation; simply callenumerate
directly onnums
to produce index-element tuples:def twoSum(self, nums, target): for i, num in enumerate(nums): for j in range(i + 1, len(nums)): if num + nums[j] == target: return [i, j]
This makes the intent much clearer: there are no duplicate variables with different names representing the same thing. It also saves unnecessary space and overhead associated with creating a list from a range.
Following on the previous item,
indx, num
andnum_lst
are confusing variable names, especially when they're all actually indices (which are technically numbers).
Efficiency
This code is inefficient, running in quadratic time, or \$\mathcal{O}(n^2)\$. Leetcode is generous to let this pass (but won't be so forgiving in the future!). The reason for this is the nested loop; for every element in your list, you iterate over every other element to draw comparisons. A linear solution should finish in ~65 ms, while this takes ~4400 ms.
Here is an efficient solution that runs in \$\mathcal{O}(n)\$ time:
hist = {} for i, n in enumerate(nums): if target - n in hist: return [hist[target-n], i] hist[n] = i
How does this work? The magic of hashing. The dictionary
hist
offers constant \$\mathcal{O}(1)\$ lookup time. Whenever we visit a new element innums
, we check to see if its sum complement is in the dictionary; else, we store it in the dictionary as anum => index
pair.This is the classic time-space tradeoff: the quadratic solution is slow but space efficient, while this solution takes more space but gains a huge boost in speed. In almost every case, choose speed over space.
For completeness, even if you were in a space-constrained environment, there is a fast solution that uses \$\mathcal{O}(1)\$ space and \$\mathcal{O}(n\log{}n)\$ time. This solution is worth knowing about for the practicality of the technique and the fact that it's a common interview follow-up. The way it works is:
- Sort
nums
. - Create two pointers representing an index at 0 and an index at
len(nums) - 1
. - Sum the elements at the pointers.
- If they produce the desired sum, return the pointer indices.
- Otherwise, if the sum is less than the target, increment the left pointer
- Otherwise, decrement the right pointer.
- Go back to step 3 unless the pointers are pointing to the same element, in which case return failure.
- Sort
Be wary of list slicing; it's often a hidden linear performance hit. Removing this slice as the nested loop code above illustrates doesn't improve the quadratic time complexity, but it does reduce overhead.
Now you're ready to try 3 Sum!