A set solution to 3 sum which slower than 80%
1
$begingroup$
I use a dummy solution to solve 3Sum problem.
that is employ set date type to handle duplicates then transform back list.
Given an array
numsof n integers, are there elements a, b innumssuch that a + b = 9? Find all unique couples in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
My codes:
from typing import List
import logging
import unittest
import random
from collections import defaultdict,Counter
##logging.disable(level=#logging.CRITICAL)
##logging.basicConfig(level=#logging.DEBUG, format="%(levelname)s %(message)s")
class Solution:
def threeSum(self, nums, target: int=0) -> List[List[int]]:
"""
:type nums: List[int]
:type target: int
"""
if len(nums) < 3: return
triplets =
if target == [0, 0, 0]:
triplets.append([0, 0, 0])
return triplets # finish fast
lookup = {nums[i]:i for i in range(len(nums))} #overwrite from the high
if len(lookup) == 1:#assert one identical element
keys = [k for k in lookup.keys()]
if keys[0] != 0:
return
else:
triplets.append([0,0,0])
return triplets
triplets_set = set()
for i in range(len(nums)):
num_1 = nums[i]
sub_target = target - num_1
# #logging.debug(f"level_1_lookup: {lookup}")
for j in range(i+1, len(nums)):
num_2 = nums[j]
num_3 = sub_target - num_2
k = lookup.get(num_3) #
if k not in {None, i, j}: #don't reproduce itself
result = [num_1, num_2, num_3]
result.sort()
result = tuple(result)
triplets_set.add(result)
triplets = [list(t) for t in triplets_set]
return triplets
Run and get report
Your runtime beats 28.86 % of python3 submissions.
Could please give hints to improve?
python algorithm
asked 29 mins ago
AliceAlice
1764
New contributor
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
1
$begingroup$
I use a dummy solution to solve 3Sum problem.
that is employ set date type to handle duplicates then transform back list.
Given an array
numsof n integers, are there elements a, b innumssuch that a + b = 9? Find all unique couples in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
My codes:
from typing import List
import logging
import unittest
import random
from collections import defaultdict,Counter
##logging.disable(level=#logging.CRITICAL)
##logging.basicConfig(level=#logging.DEBUG, format="%(levelname)s %(message)s")
class Solution:
def threeSum(self, nums, target: int=0) -> List[List[int]]:
"""
:type nums: List[int]
:type target: int
"""
if len(nums) < 3: return
triplets =
if target == [0, 0, 0]:
triplets.append([0, 0, 0])
return triplets # finish fast
lookup = {nums[i]:i for i in range(len(nums))} #overwrite from the high
if len(lookup) == 1:#assert one identical element
keys = [k for k in lookup.keys()]
if keys[0] != 0:
return
else:
triplets.append([0,0,0])
return triplets
triplets_set = set()
for i in range(len(nums)):
num_1 = nums[i]
sub_target = target - num_1
# #logging.debug(f"level_1_lookup: {lookup}")
for j in range(i+1, len(nums)):
num_2 = nums[j]
num_3 = sub_target - num_2
k = lookup.get(num_3) #
if k not in {None, i, j}: #don't reproduce itself
result = [num_1, num_2, num_3]
result.sort()
result = tuple(result)
triplets_set.add(result)
triplets = [list(t) for t in triplets_set]
return triplets
Run and get report
Your runtime beats 28.86 % of python3 submissions.
Could please give hints to improve?
python algorithm
asked 29 mins ago
AliceAlice
1764
New contributor
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
1
1
1
$begingroup$
I use a dummy solution to solve 3Sum problem.
that is employ set date type to handle duplicates then transform back list.
Given an array
numsof n integers, are there elements a, b innumssuch that a + b = 9? Find all unique couples in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
My codes:
from typing import List
import logging
import unittest
import random
from collections import defaultdict,Counter
##logging.disable(level=#logging.CRITICAL)
##logging.basicConfig(level=#logging.DEBUG, format="%(levelname)s %(message)s")
class Solution:
def threeSum(self, nums, target: int=0) -> List[List[int]]:
"""
:type nums: List[int]
:type target: int
"""
if len(nums) < 3: return
triplets =
if target == [0, 0, 0]:
triplets.append([0, 0, 0])
return triplets # finish fast
lookup = {nums[i]:i for i in range(len(nums))} #overwrite from the high
if len(lookup) == 1:#assert one identical element
keys = [k for k in lookup.keys()]
if keys[0] != 0:
return
else:
triplets.append([0,0,0])
return triplets
triplets_set = set()
for i in range(len(nums)):
num_1 = nums[i]
sub_target = target - num_1
# #logging.debug(f"level_1_lookup: {lookup}")
for j in range(i+1, len(nums)):
num_2 = nums[j]
num_3 = sub_target - num_2
k = lookup.get(num_3) #
if k not in {None, i, j}: #don't reproduce itself
result = [num_1, num_2, num_3]
result.sort()
result = tuple(result)
triplets_set.add(result)
triplets = [list(t) for t in triplets_set]
return triplets
Run and get report
Your runtime beats 28.86 % of python3 submissions.
Could please give hints to improve?
python algorithm
asked 29 mins ago
AliceAlice
1764
New contributor
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I use a dummy solution to solve 3Sum problem.
that is employ set date type to handle duplicates then transform back list.
Given an array
numsof n integers, are there elements a, b innumssuch that a + b = 9? Find all unique couples in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
My codes:
from typing import List
import logging
import unittest
import random
from collections import defaultdict,Counter
##logging.disable(level=#logging.CRITICAL)
##logging.basicConfig(level=#logging.DEBUG, format="%(levelname)s %(message)s")
class Solution:
def threeSum(self, nums, target: int=0) -> List[List[int]]:
"""
:type nums: List[int]
:type target: int
"""
if len(nums) < 3: return
triplets =
if target == [0, 0, 0]:
triplets.append([0, 0, 0])
return triplets # finish fast
lookup = {nums[i]:i for i in range(len(nums))} #overwrite from the high
if len(lookup) == 1:#assert one identical element
keys = [k for k in lookup.keys()]
if keys[0] != 0:
return
else:
triplets.append([0,0,0])
return triplets
triplets_set = set()
for i in range(len(nums)):
num_1 = nums[i]
sub_target = target - num_1
# #logging.debug(f"level_1_lookup: {lookup}")
for j in range(i+1, len(nums)):
num_2 = nums[j]
num_3 = sub_target - num_2
k = lookup.get(num_3) #
if k not in {None, i, j}: #don't reproduce itself
result = [num_1, num_2, num_3]
result.sort()
result = tuple(result)
triplets_set.add(result)
triplets = [list(t) for t in triplets_set]
return triplets
Run and get report
Your runtime beats 28.86 % of python3 submissions.
Could please give hints to improve?
python algorithm
python algorithm
asked 29 mins ago
AliceAlice
1764
New contributor
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 29 mins ago
AliceAlice
1764
New contributor
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 29 mins ago
AliceAlice
1764
New contributor
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 29 mins ago
AliceAlice
1764
asked 29 mins ago
AliceAlice
1764
1764
New contributor
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
0
active
oldest
votes
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.
draft saved
draft discarded
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%2f216207%2fa-set-solution-to-3-sum-which-slower-than-80%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Alice is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f216207%2fa-set-solution-to-3-sum-which-slower-than-80%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
