Timeline for 3 sum implementation in python 2.7
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 25, 2016 at 11:07 | comment | added | Peilonrayz♦ |
@LinMa Both mine and yours are \$O(n^2)\$. Try the code without combinations_with_replacement, and you'll see it doesn't work in all cases, such as ones that have duplicate values.
|
|
| Dec 25, 2016 at 5:48 | comment | added | Lin Ma |
BTW, another thing I am confused is, why you are using combinations_with_replacement other than itertools.combinations, I think combinations_with_replacement considers repeated elements, but list(sorted(count)) should be unique which is dict keys?
|
|
| Dec 25, 2016 at 5:40 | comment | added | Lin Ma |
Thanks Peilonrayz, appreciate you pointed out so many areas for improvements and vote up. There is only one thing I do not quite agree, which is if you enumerate all 3 number combinations, time complexity is O(n^2) which is less than mine (which is O(n*lgn))?
|
|
| Dec 22, 2016 at 10:48 | history | answered | Peilonrayz♦ | CC BY-SA 3.0 |