i am supposed to find three numbers in an array whose sum is equal to a target sum given
something like this:
[12, 3, 1, 2, -6, 5, -8, 6]-array
0-targetsum
[12, 3, 1, 2, -6, 5, -8, 6]-output
i tried a hashmap for this:
def threeNumberSum(array, targetSum):
hashtable={}
output=[]
for i in range(len(array)-1):
hashtable[array[i]]=True
for i in range(len(array)-1):
for j in range(len(array)-1):
if i==j:
continue
y=targetSum-array[i]-array[j]
if y in hashtable and (y!=array[i] and y!=array[j]):
output.append(sorted([array[i],array[j],y]))
return output
print(threeNumberSum([12, 3, 1, 2, -6, 5, -8, 6],0))
def threeNumberSum(array, targetSum):
hashtable={}
output=[]
for i in range(len(array)-1):
hashtable[array[i]]=True
for i in range(len(array)):
for j in range(len(array)):
if i==j:
continue
y=targetSum-array[i]-array[j]
if y in hashtable and (y!=array[i] and y!=array[j]):
solution=sorted([array[i],array[j],y])
if solution not in output:
output.append(solution)
def threeSum(array):
hashtable={}
output=[]
for i in range(len(array)-1):
hashtable[array[i]]=True
for i in range(len(array)):
for j in range(len(array)):
if i==j:
continue
y=array[i]-array[j]
if y in hashtable and (y!=array[i] and y!=array[j]):
solution=sorted([array[i],array[j],y])
if solution not in output:
I am getting:
[[-1, -1, 0], [-1, 0, 1], [-1, 1, 2]]
the first item in output list is only possible when i==j case
class Solution:
def threeSum(self, array: List[int]) -> List[List[int]]:
hashtable={}
output=[]
for i in range(len(array)):
hashtable[array[i]]=i
for i in range(len(array)):
for j in range(len(array)):
if i==j:
continue
y=0-(array[i]+array[j])
if y in hashtable and (hashtable[y]!=i and hashtable[y]!=j):
solution=sorted([array[i],array[j],y])
if solution not in output:
@Aladdin I got a bit further using a dictionary to check for duplicates:
class Solution:
def __init__(self):
self.dups = {}
def threeSum(self, nums: List[int]) -> List[List[int]]:
hashtable={}
output=[]
for i in range(len(nums)):
hashtable[nums[i]]=i
for i in range(len(nums)):
for j in range(len(nums)):
if i==j:
continue
y=0-(nums[i]+nums[j])
if y in hashtable and (hashtable[y]!=i and hashtable[y]!=j):
solution=sorted([nums[i],nums[j],y])
@Aladdin I think I've figured out how to solve it. The failing case has lots of the same number, i.e. 0, so it's triggering lots of duplicate checks and that is using up the time.
But we are only taking three numbers, so there is no point in the list having more than three zeroes or more than two identical non-zero numbers. So at the start we should process the list and remove unnecessary extra numbers. This can be done when you're building the hash table at the start.
This is the code. We can discuss how it works whenever you want.
class Solution:
def threeSum(self, nums):
output=[]
# Find the number of occurrences of each number
hashtable={}
for num in nums:
if not num in hashtable:
hashtable[num] = 1
elif num != 0 and hashtable[num] < 2:
hashtable[num] += 1
elif num == 0 and hashtable[num] < 3:
hashtable[num] += 1
# Build a new list of the numbers in the hash table but with no
# more than three occurrences of each number