Hash table solution to twoSum
$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
New contributor
$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
New contributor
$endgroup$
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
yesterday
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
New contributor
$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
New contributor
New contributor
edited yesterday
200_success
130k17155419
130k17155419
New contributor
asked yesterday
AliceAlice
1774
1774
New contributor
New contributor
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
yesterday
add a comment |
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
yesterday
1
1
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
yesterday
$begingroup$
Take care not to misuse the term refactoring when you just mean rewriting.
$endgroup$
– 200_success
yesterday
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 normally
nums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279
nums_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$
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
17 hours ago
1
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
12 hours ago
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$
1
$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
yesterday
$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
10 hours ago
$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 $frac{n^2}{2}$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
6 hours ago
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
});
}
});
Alice is a new contributor. Be nice, and check out our Code of Conduct.
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 normally
nums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279
nums_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$
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
17 hours ago
1
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
12 hours ago
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 normally
nums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279
nums_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$
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
17 hours ago
1
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
12 hours ago
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 normally
nums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279
nums_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 normally
nums_d[nums[i]] = [i]
When you need both the
index
and theelement
use enumerate see PEP279
nums_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 yesterday
ielyamani
355213
355213
answered yesterday
LudisposedLudisposed
8,95822267
8,95822267
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
17 hours ago
1
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
12 hours ago
add a comment |
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
17 hours ago
1
$begingroup$
@Graipher True, adefaultdict
might be more appropriate there.
$endgroup$
– Ludisposed
12 hours ago
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
17 hours ago
$begingroup$
Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append.
$endgroup$
– Graipher
17 hours ago
1
1
$begingroup$
@Graipher True, a
defaultdict
might be more appropriate there.$endgroup$
– Ludisposed
12 hours ago
$begingroup$
@Graipher True, a
defaultdict
might be more appropriate there.$endgroup$
– Ludisposed
12 hours ago
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$
1
$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
yesterday
$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
10 hours ago
$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 $frac{n^2}{2}$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
6 hours ago
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$
1
$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
yesterday
$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
10 hours ago
$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 $frac{n^2}{2}$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
6 hours ago
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 yesterday
answered yesterday
RolfBlyRolfBly
592418
592418
1
$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
yesterday
$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
10 hours ago
$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 $frac{n^2}{2}$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
6 hours ago
add a comment |
1
$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
yesterday
$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
10 hours ago
$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 $frac{n^2}{2}$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
6 hours ago
1
1
$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
yesterday
$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
yesterday
$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
10 hours ago
$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
10 hours ago
$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 $frac{n^2}{2}$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
6 hours ago
$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 $frac{n^2}{2}$ iterations. And so it's mostly just a vague guess at performance.
$endgroup$
– Peilonrayz
6 hours ago
add a comment |
Alice is a new contributor. Be nice, and check out our Code of Conduct.
Alice is a new contributor. Be nice, and check out our Code of Conduct.
Alice is a new contributor. Be nice, and check out our Code of Conduct.
Alice is a new contributor. Be nice, and check out our Code of Conduct.
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
yesterday