Solution to Two-Sum by LeetCode

24 Mar

Question: http://oj.leetcode.com/problems/two-sum/

Question Name: Two Sum

Futher reading: http://stackoverflow.com/questions/8334981/find-pair-of-numbers-in-array-that-add-to-given-sum

10 Replies to “Solution to Two-Sum by LeetCode

  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.

  2. 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…

          • 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.

  3. Just come over and say hi:

Leave a Reply

Your email address will not be published. Required fields are marked *