Timeline for Finding two numbers that add to a given total
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2018 at 15:09 | comment | added | TheBlackCat | @TobySpeight Again, this is from three years ago. It is a little late for that now. | |
| Oct 25, 2018 at 15:03 | comment | added | Toby Speight | Well, if that was the requirement, then the question should have been closed as clearly not working! | |
| Oct 25, 2018 at 14:51 | comment | added | TheBlackCat | @TobySpeight OP said he wanted the numbers. This was accepted as the correct answer 3 years ago so it was probably what the OP wanted. | |
| Oct 25, 2018 at 13:37 | comment | added | Toby Speight | This appears to output the values that sum to the target total, rather than the indices of those values as in the original code. | |
| Jun 17, 2015 at 5:09 | vote | accept | toy | ||
| Jun 16, 2015 at 14:54 | comment | added | user2023861 | @TheBlackCat, I get it now. My python is weak. | |
| Jun 16, 2015 at 13:39 | comment | added | TheBlackCat |
@user2023861 I am not using arrays, I am using sets. Yes, for arrays it is O(n*n). But for sets the same operation is O(n). This is because it uses a hash table for value lookups. Looking up a value in an array is a O(n), but looking up a value in a well-structured hash table is O(1) (in CPython, hash tables of integers are always well-structured). Since it is doing a O(1) operation on each element of one of the sets, it is a O(1*n) operation overall, or O(n). You can see this in the official python Time Complexity page.
|
|
| Jun 16, 2015 at 13:29 | comment | added | user2023861 |
@TheBlackCat, in your example, after you've subtracted the remaining numbers from the target, is your array {101,98,180,143,144,127,123,92}? And from this, are you saying you find the numbers that are also present in the original list {80,98,83,92,1,38,37,54,58,89}? If that's your algorithm, I don't see how that's not O(n*n). That last step involves scanning through one array for each item in the other array.
|
|
| Jun 15, 2015 at 20:33 | history | edited | TheBlackCat | CC BY-SA 3.0 |
Add big-O notation
|
| Jun 15, 2015 at 20:15 | history | edited | TheBlackCat | CC BY-SA 3.0 |
short-circuit case where (n2, n2) in pairs
|
| Jun 15, 2015 at 20:00 | history | edited | TheBlackCat | CC BY-SA 3.0 |
use greater/less than split
|
| Jun 15, 2015 at 19:33 | comment | added | TheBlackCat | @GarethRees I added an optional bit of code to handle this case. | |
| Jun 15, 2015 at 19:33 | history | edited | TheBlackCat | CC BY-SA 3.0 |
Use list.count
|
| Jun 15, 2015 at 19:25 | comment | added | Gareth Rees |
numbers has only one element: it can't possibly contain two numbers that add up to anything. In other words: the items have to be chosen without replacement. See the original post, which is careful only to consider items at different indexes in the list.
|
|
| Jun 15, 2015 at 19:18 | comment | added | TheBlackCat | It returns [(1,1)]. Is this not the expect value in such a case? | |
| Jun 15, 2015 at 19:17 | history | edited | TheBlackCat | CC BY-SA 3.0 |
Add explanation
|
| Jun 15, 2015 at 19:17 | comment | added | Gareth Rees |
This goes wrong in the case n = 2 and numbers = [1].
|
|
| Jun 15, 2015 at 19:13 | history | answered | TheBlackCat | CC BY-SA 3.0 |