Question Name: Two Sum
Futher reading: http://stackoverflow.com/questions/8334981/find-pair-of-numbers-in-array-that-add-to-given-sum
Solution to Two-Sum by LeetCode
# @return a tuple, (index1, index2)
def twoSum(self, num, target):
index1, index2, total = 0, len(num)-1, 0
sortedNum = sorted(enumerate(num), key=lambda x:x)
while index1 != index2:
total = sortedNum[index1] + sortedNum[index2]
if total == target:
if sortedNum[index1] > sortedNum[index2] :
return (sortedNum[index2]+1, sortedNum[index1]+1)
return (sortedNum[index1]+1, sortedNum[index2]+1)
elif total > target:
index2 -= 1
index1 += 1
return (-1, -1)
let’s make it a bit shorter…
First of all, thanks for sharing your idea! If you could check the solution to get 100/100 before posting it, it would be better.
Your solution will fail in performance test, because it did not skip the duplicate items.
Actually, this code won’t compile in LeetCode, for some unknown reasons. There is a diff in case of ‘next’ usage in python 2 and 3 – but both do not pass compilation.
I don’t care though, indeed wanted to share a solution which is an elegant and consise – using Python obligates 🙂 Additionally, using a ‘class’ is ridiculous, too…
Regarding performance – here is a bit improved version – it uses a generator instead of creating a real list of pairs, so duplicates do not matter – just get’s never generated:
Compile Error is because of the “import itertools”. You could use it without importing. The test stub will do it automatically. BTW, LeetCode is using Python2.
You code still cannot pass the test for performance. “For every complex problem there is an answer that is clear, simple, and wrong.”
Thanks for your sharing anyway! (I did not know the itertools.combinations before, THX!)
And why is the reason it does not pass the performance test?
Is it because of the space taken? If so, the verifyier seems to be wrong on it since there are no dicts or lists really created here – all are generators…
As I said, you have to skip the duplicate items to pass the performance test. But you did not.
But you do realize that these duplicates are never instantiated, don’t you? They would be if it gets iterated through the whole generator, but it ends on the first match.
Before the first match, you might have already met with many duplicate combinations. For example, the given array is [1,1,2,2,6,6] and target is 4. If using your solution,
You will try to test the combination of (1, 6) for many times. It IS the reason why your solution failed. Program never lies.
Just come over and say hi: