This week the class learned about functions and how to use them. Functions have access to all global variables unless a variable with the same name is declared in the function. This will make a temporary variable that is only accessible within the function call. The global keyword makes if so that a variable declared in a function(method) accesses a global variable. Functions are useful for recursive functions and generally a good practice for coders.
Solution to problem on slide 4:
Maintain a map that stores the values you need in order to sum up to 20, in the map store the indices of that value retreive that value onces you have found a valid pair.
class Solution(object):
def twoSum(self, nums, target):
nn = {} #needed numbers
for i,v in enumerate(nums):
if nn.has_key(v):
return nn[v],i
else:
nn[target-v] = iSolution to problem on slide 5:
- store the positive, negative and zeros in a list.
- if you have at least one zero, find all the positive and negative numbers that add to zero, so you would get x,-x,0
- then iterate through all of the positive numbers and use twoSum solution to find all pairs of numbers that would add with that number to make it zero
- do the same thing with the negative numbers
use a set for result in case you have repetitive solutions.
O(n^2 +n) complexity
class Solution:
def threeSum(self, nums):
res = set()
p, n, z = [], [], []
for i in nums:
if i > 0:
p.append(i)
elif i < 0:
n.append(i)
else:
z.append(i)
P, N = set(p), set(n)
if z:
for i in n:
if -1 * i in P:
res.add((i, 0, -i))
if len(z) >= 3:
res.add((0, 0, 0))
for i in range(len(n)):
for j in range(i+1, len(n)):
target = -1 * (n[i] + n[j])
if target in P:
res.add(tuple(sorted([n[i], n[j], target])))
for i in range(len(p)):
for j in range(i+1, len(p)):
target = -1 * (p[i] + p[j])
if target in N:
res.add(tuple(sorted([p[i], p[j], target])))
return res