Hash table solution to twoSumA One-Pass Hash Table Solution to twoSumQuick Sum TopCoder (Brute Force solution)FindTwoSums using TupleLeetcode 15. 3 SumFind two values that add up to the sum3-Sum Problem in PythonTwo Sum LeetcodePython 3 two-sum performanceUnique character lookupLeetcode Two Sum code in PythonFaster code for leetcode reverse int
Can I interfere when another PC is about to be attacked?
Possibly bubble sort algorithm
How to make payment on the internet without leaving a money trail?
Is Social Media Science Fiction?
Why doesn't Newton's third law mean a person bounces back to where they started when they hit the ground?
What makes Graph invariants so useful/important?
How can the DM most effectively choose 1 out of an odd number of players to be targeted by an attack or effect?
Japan - Plan around max visa duration
Prevent a directory in /tmp from being deleted
What would happen to a modern skyscraper if it rains micro blackholes?
How do I create uniquely male characters?
Schwarzchild Radius of the Universe
How can I fix this gap between bookcases I made?
whey we use polarized capacitor?
How do you conduct xenoanthropology after first contact?
Download, install and reboot computer at night if needed
Why is this code 6.5x slower with optimizations enabled?
Why don't electron-positron collisions release infinite energy?
Why is an old chain unsafe?
A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?
Copenhagen passport control - US citizen
"which" command doesn't work / path of Safari?
What Brexit solution does the DUP want?
Could a US political party gain complete control over the government by removing checks & balances?
Hash table solution to twoSum
A One-Pass Hash Table Solution to twoSumQuick Sum TopCoder (Brute Force solution)FindTwoSums using TupleLeetcode 15. 3 SumFind two values that add up to the sum3-Sum Problem in PythonTwo Sum LeetcodePython 3 two-sum performanceUnique character lookupLeetcode Two Sum code in PythonFaster code for leetcode reverse int
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
I try the most to solve a twoSum problem in leetcode
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
The plan:
- brute force to iterate len(nums) O(n)
- search for target - num[i] with a hash table O(1)
Implement
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)
for i in range(len(nums)):
sub_target = target - nums[i]
nums_d[nums[i]].pop(0) #remove the fixer
result = nums_d.get(sub_target)#hash table to search
if result:
return [i, result[0]]
return []
I strives hours for this solution but found that answer accepted but not passed Score 60.
Runtime: 60 ms, faster than 46.66% of Python3 online submissions for Two Sum.
Memory Usage: 16.1 MB, less than 5.08% of Python3 online submissions for Two Sum.
I want to refactor the codes so that to achieve at least faster than 60%.
Could you please provide hints?
python performance algorithm python-3.x k-sum
$endgroup$
add a comment |
$begingroup$
I try the most to solve a twoSum problem in leetcode
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
The plan:
- brute force to iterate len(nums) O(n)
- search for target - num[i] with a hash table O(1)
Implement
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)
for i in range(len(nums)):
sub_target = target - nums[i]
nums_d[nums[i]].pop(0) #remove the fixer
result = nums_d.get(sub_target)#hash table to search
if result:
return [i, result[0]]
return []
I strives hours for this solution but found that answer accepted but not passed Score 60.
Runtime: 60 ms, faster than 46.66% of Python3 online submissions for Two Sum.
Memory Usage: 16.1 MB, less than 5.08% of Python3 online submissions for Two Sum.
I want to refactor the codes so that to achieve at least faster than 60%.
Could you please provide hints?
python performance algorithm python-3.x k-sum
$endgroup$
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
Mar 22 at 12:26
add a comment |
$begingroup$
I try the most to solve a twoSum problem in leetcode
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
The plan:
- brute force to iterate len(nums) O(n)
- search for target - num[i] with a hash table O(1)
Implement
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)
for i in range(len(nums)):
sub_target = target - nums[i]
nums_d[nums[i]].pop(0) #remove the fixer
result = nums_d.get(sub_target)#hash table to search
if result:
return [i, result[0]]
return []
I strives hours for this solution but found that answer accepted but not passed Score 60.
Runtime: 60 ms, faster than 46.66% of Python3 online submissions for Two Sum.
Memory Usage: 16.1 MB, less than 5.08% of Python3 online submissions for Two Sum.
I want to refactor the codes so that to achieve at least faster than 60%.
Could you please provide hints?
python performance algorithm python-3.x k-sum
$endgroup$
I try the most to solve a twoSum problem in leetcode
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
The plan:
- brute force to iterate len(nums) O(n)
- search for target - num[i] with a hash table O(1)
Implement
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)
for i in range(len(nums)):
sub_target = target - nums[i]
nums_d[nums[i]].pop(0) #remove the fixer
result = nums_d.get(sub_target)#hash table to search
if result:
return [i, result[0]]
return []
I strives hours for this solution but found that answer accepted but not passed Score 60.
Runtime: 60 ms, faster than 46.66% of Python3 online submissions for Two Sum.
Memory Usage: 16.1 MB, less than 5.08% of Python3 online submissions for Two Sum.
I want to refactor the codes so that to achieve at least faster than 60%.
Could you please provide hints?
python performance algorithm python-3.x k-sum
python performance algorithm python-3.x k-sum
edited Mar 22 at 12:25
200_success
131k17157422
131k17157422
asked Mar 22 at 5:27
AliceAlice
3206
3206
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
Mar 22 at 12:26
add a comment |
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
Mar 22 at 12:26
1
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
Mar 22 at 12:26
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
Mar 22 at 12:26
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
First some stylistic points
nums_d.setdefault(nums[i], []).append(i)
The
setdefault
is unnecessary here, you can assign a list normallynums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)nums_d =
for i, e in enumerate(nums):
nums_d[e] = [i]Use comprehension when possible (They use the C style looping and is considered to be faster)
nums_d = e: [i] for i, e in enumerate(nums)
Hint
You loop over nums twice, but this can be done in one loop! To make it O(n)
Whenever you visit a new element in nums ->
Check if it's sum complement is in nums_d
, else add the target - element
to the dictionary with the index as value t - e : i
nums_d =
for i, e in enumerate(nums):
if e in nums_d:
return [nums_d[e], i]
nums_d[target - e] = i
$endgroup$
1
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
Mar 23 at 11:17
2
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
Mar 23 at 16:28
$begingroup$
$O(2n) = O(n).$
$endgroup$
– Solomon Ucko
Mar 29 at 0:23
add a comment |
$begingroup$
You may assume that each input would have exactly one solution.
So there's no need to iterate over num
twice. In fact, you won't even iterate over it for the full range, because you can return when you found the solution.
With the input given, I'd try this:
nums = [2, 7, 11, 15]
target = 9
def twoSum(nums, target):
for i in nums:
for m in nums[nums.index(i)+1:]:
if i + m == target:
return [nums.index(i), nums.index(m)]
print(twoSum(nums, target))
Say i + m
is your target twoSum, you iterate over nums for each i and then look in the rest of num if there's any m
for which i + m = target
, and return when found.
Edit: This fails if you have duplicate integers in nums that add up to target, and it'll be slower if the solution is two elements near the end of nums.
Also: thank you for mentioning Leetcode, it's new to me. Nice!
$endgroup$
2
$begingroup$
Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes $O(n^2)$ time and either $O(n)$ or $O(n^2)$ memory, depending on the GC. Where in the question it runs in $O(n)$ time and space. Yours is however easier to understand.
$endgroup$
– Peilonrayz
Mar 22 at 22:29
$begingroup$
Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here?
$endgroup$
– RolfBly
Mar 23 at 18:54
$begingroup$
Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case $fracn^22$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
Mar 23 at 22:19
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215975%2fhash-table-solution-to-twosum%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First some stylistic points
nums_d.setdefault(nums[i], []).append(i)
The
setdefault
is unnecessary here, you can assign a list normallynums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)nums_d =
for i, e in enumerate(nums):
nums_d[e] = [i]Use comprehension when possible (They use the C style looping and is considered to be faster)
nums_d = e: [i] for i, e in enumerate(nums)
Hint
You loop over nums twice, but this can be done in one loop! To make it O(n)
Whenever you visit a new element in nums ->
Check if it's sum complement is in nums_d
, else add the target - element
to the dictionary with the index as value t - e : i
nums_d =
for i, e in enumerate(nums):
if e in nums_d:
return [nums_d[e], i]
nums_d[target - e] = i
$endgroup$
1
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
Mar 23 at 11:17
2
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
Mar 23 at 16:28
$begingroup$
$O(2n) = O(n).$
$endgroup$
– Solomon Ucko
Mar 29 at 0:23
add a comment |
$begingroup$
First some stylistic points
nums_d.setdefault(nums[i], []).append(i)
The
setdefault
is unnecessary here, you can assign a list normallynums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)nums_d =
for i, e in enumerate(nums):
nums_d[e] = [i]Use comprehension when possible (They use the C style looping and is considered to be faster)
nums_d = e: [i] for i, e in enumerate(nums)
Hint
You loop over nums twice, but this can be done in one loop! To make it O(n)
Whenever you visit a new element in nums ->
Check if it's sum complement is in nums_d
, else add the target - element
to the dictionary with the index as value t - e : i
nums_d =
for i, e in enumerate(nums):
if e in nums_d:
return [nums_d[e], i]
nums_d[target - e] = i
$endgroup$
1
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
Mar 23 at 11:17
2
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
Mar 23 at 16:28
$begingroup$
$O(2n) = O(n).$
$endgroup$
– Solomon Ucko
Mar 29 at 0:23
add a comment |
$begingroup$
First some stylistic points
nums_d.setdefault(nums[i], []).append(i)
The
setdefault
is unnecessary here, you can assign a list normallynums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)nums_d =
for i, e in enumerate(nums):
nums_d[e] = [i]Use comprehension when possible (They use the C style looping and is considered to be faster)
nums_d = e: [i] for i, e in enumerate(nums)
Hint
You loop over nums twice, but this can be done in one loop! To make it O(n)
Whenever you visit a new element in nums ->
Check if it's sum complement is in nums_d
, else add the target - element
to the dictionary with the index as value t - e : i
nums_d =
for i, e in enumerate(nums):
if e in nums_d:
return [nums_d[e], i]
nums_d[target - e] = i
$endgroup$
First some stylistic points
nums_d.setdefault(nums[i], []).append(i)
The
setdefault
is unnecessary here, you can assign a list normallynums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279nums_d =
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)nums_d =
for i, e in enumerate(nums):
nums_d[e] = [i]Use comprehension when possible (They use the C style looping and is considered to be faster)
nums_d = e: [i] for i, e in enumerate(nums)
Hint
You loop over nums twice, but this can be done in one loop! To make it O(n)
Whenever you visit a new element in nums ->
Check if it's sum complement is in nums_d
, else add the target - element
to the dictionary with the index as value t - e : i
nums_d =
for i, e in enumerate(nums):
if e in nums_d:
return [nums_d[e], i]
nums_d[target - e] = i
edited Mar 22 at 11:16
ielyamani
372213
372213
answered Mar 22 at 8:47
LudisposedLudisposed
9,13822268
9,13822268
1
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
Mar 23 at 11:17
2
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
Mar 23 at 16:28
$begingroup$
$O(2n) = O(n).$
$endgroup$
– Solomon Ucko
Mar 29 at 0:23
add a comment |
1
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
Mar 23 at 11:17
2
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
Mar 23 at 16:28
$begingroup$
$O(2n) = O(n).$
$endgroup$
– Solomon Ucko
Mar 29 at 0:23
1
1
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
Mar 23 at 11:17
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
Mar 23 at 11:17
2
2
$begingroup$
@Graipher True, a
defaultdict
might be more appropriate there.$endgroup$
– Ludisposed
Mar 23 at 16:28
$begingroup$
@Graipher True, a
defaultdict
might be more appropriate there.$endgroup$
– Ludisposed
Mar 23 at 16:28
$begingroup$
$O(2n) = O(n).$
$endgroup$
– Solomon Ucko
Mar 29 at 0:23
$begingroup$
$O(2n) = O(n).$
$endgroup$
– Solomon Ucko
Mar 29 at 0:23
add a comment |
$begingroup$
You may assume that each input would have exactly one solution.
So there's no need to iterate over num
twice. In fact, you won't even iterate over it for the full range, because you can return when you found the solution.
With the input given, I'd try this:
nums = [2, 7, 11, 15]
target = 9
def twoSum(nums, target):
for i in nums:
for m in nums[nums.index(i)+1:]:
if i + m == target:
return [nums.index(i), nums.index(m)]
print(twoSum(nums, target))
Say i + m
is your target twoSum, you iterate over nums for each i and then look in the rest of num if there's any m
for which i + m = target
, and return when found.
Edit: This fails if you have duplicate integers in nums that add up to target, and it'll be slower if the solution is two elements near the end of nums.
Also: thank you for mentioning Leetcode, it's new to me. Nice!
$endgroup$
2
$begingroup$
Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes $O(n^2)$ time and either $O(n)$ or $O(n^2)$ memory, depending on the GC. Where in the question it runs in $O(n)$ time and space. Yours is however easier to understand.
$endgroup$
– Peilonrayz
Mar 22 at 22:29
$begingroup$
Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here?
$endgroup$
– RolfBly
Mar 23 at 18:54
$begingroup$
Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case $fracn^22$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
Mar 23 at 22:19
add a comment |
$begingroup$
You may assume that each input would have exactly one solution.
So there's no need to iterate over num
twice. In fact, you won't even iterate over it for the full range, because you can return when you found the solution.
With the input given, I'd try this:
nums = [2, 7, 11, 15]
target = 9
def twoSum(nums, target):
for i in nums:
for m in nums[nums.index(i)+1:]:
if i + m == target:
return [nums.index(i), nums.index(m)]
print(twoSum(nums, target))
Say i + m
is your target twoSum, you iterate over nums for each i and then look in the rest of num if there's any m
for which i + m = target
, and return when found.
Edit: This fails if you have duplicate integers in nums that add up to target, and it'll be slower if the solution is two elements near the end of nums.
Also: thank you for mentioning Leetcode, it's new to me. Nice!
$endgroup$
2
$begingroup$
Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes $O(n^2)$ time and either $O(n)$ or $O(n^2)$ memory, depending on the GC. Where in the question it runs in $O(n)$ time and space. Yours is however easier to understand.
$endgroup$
– Peilonrayz
Mar 22 at 22:29
$begingroup$
Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here?
$endgroup$
– RolfBly
Mar 23 at 18:54
$begingroup$
Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case $fracn^22$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
Mar 23 at 22:19
add a comment |
$begingroup$
You may assume that each input would have exactly one solution.
So there's no need to iterate over num
twice. In fact, you won't even iterate over it for the full range, because you can return when you found the solution.
With the input given, I'd try this:
nums = [2, 7, 11, 15]
target = 9
def twoSum(nums, target):
for i in nums:
for m in nums[nums.index(i)+1:]:
if i + m == target:
return [nums.index(i), nums.index(m)]
print(twoSum(nums, target))
Say i + m
is your target twoSum, you iterate over nums for each i and then look in the rest of num if there's any m
for which i + m = target
, and return when found.
Edit: This fails if you have duplicate integers in nums that add up to target, and it'll be slower if the solution is two elements near the end of nums.
Also: thank you for mentioning Leetcode, it's new to me. Nice!
$endgroup$
You may assume that each input would have exactly one solution.
So there's no need to iterate over num
twice. In fact, you won't even iterate over it for the full range, because you can return when you found the solution.
With the input given, I'd try this:
nums = [2, 7, 11, 15]
target = 9
def twoSum(nums, target):
for i in nums:
for m in nums[nums.index(i)+1:]:
if i + m == target:
return [nums.index(i), nums.index(m)]
print(twoSum(nums, target))
Say i + m
is your target twoSum, you iterate over nums for each i and then look in the rest of num if there's any m
for which i + m = target
, and return when found.
Edit: This fails if you have duplicate integers in nums that add up to target, and it'll be slower if the solution is two elements near the end of nums.
Also: thank you for mentioning Leetcode, it's new to me. Nice!
edited Mar 22 at 10:43
answered Mar 22 at 8:02
RolfBlyRolfBly
592418
592418
2
$begingroup$
Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes $O(n^2)$ time and either $O(n)$ or $O(n^2)$ memory, depending on the GC. Where in the question it runs in $O(n)$ time and space. Yours is however easier to understand.
$endgroup$
– Peilonrayz
Mar 22 at 22:29
$begingroup$
Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here?
$endgroup$
– RolfBly
Mar 23 at 18:54
$begingroup$
Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case $fracn^22$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
Mar 23 at 22:19
add a comment |
2
$begingroup$
Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes $O(n^2)$ time and either $O(n)$ or $O(n^2)$ memory, depending on the GC. Where in the question it runs in $O(n)$ time and space. Yours is however easier to understand.
$endgroup$
– Peilonrayz
Mar 22 at 22:29
$begingroup$
Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here?
$endgroup$
– RolfBly
Mar 23 at 18:54
$begingroup$
Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case $fracn^22$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
Mar 23 at 22:19
2
2
$begingroup$
Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes $O(n^2)$ time and either $O(n)$ or $O(n^2)$ memory, depending on the GC. Where in the question it runs in $O(n)$ time and space. Yours is however easier to understand.
$endgroup$
– Peilonrayz
Mar 22 at 22:29
$begingroup$
Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes $O(n^2)$ time and either $O(n)$ or $O(n^2)$ memory, depending on the GC. Where in the question it runs in $O(n)$ time and space. Yours is however easier to understand.
$endgroup$
– Peilonrayz
Mar 22 at 22:29
$begingroup$
Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here?
$endgroup$
– RolfBly
Mar 23 at 18:54
$begingroup$
Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here?
$endgroup$
– RolfBly
Mar 23 at 18:54
$begingroup$
Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case $fracn^22$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
Mar 23 at 22:19
$begingroup$
Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case $fracn^22$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
Mar 23 at 22:19
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215975%2fhash-table-solution-to-twosum%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
Mar 22 at 12:26