Solve two sum with a hash table

2 files changed, 39 insertions, 0 deletions

diff --git a/2020/08/17/README.md b/2020/08/17/README.md
new file mode 100644
index 0000000..1203926
--- /dev/null
+++ b/2020/08/17/README.md
@@ -0,0 +1,14 @@
+You are given a list of numbers, and a target number k.
+Return whether or not there are two numbers in the list that add up to k.
+
+Example:
+Given [4, 7, 1 , -3, 2] and k = 5,
+return true since 4 + 1 = 5.
+
+def two_sum(list, k):
+  # Fill this in.
+
+print two_sum([4,7,1,-3,2], 5)
+# True
+
+Try to do it in a single pass of the list.
diff --git a/2020/08/17/main.rb b/2020/08/17/main.rb
new file mode 100644
index 0000000..34ba708
--- /dev/null
+++ b/2020/08/17/main.rb
@@ -0,0 +1,25 @@
+def assert(x)
+  raise x.inspect unless x
+end
+
+class Solution
+  # time: O(n)
+  # space: O(n)
+  def self.run(items, k)
+    nums = {}
+
+    for i in (0...items.size)
+      nums[items[i]] = true
+      return true if nums[k - items[i]]
+    end
+
+    false
+  end
+end
+=begin
+ h
+|4|7|1|-3|2|
+=end
+
+assert(Solution.run([4, 7, 1, -3, 2], 5))
+puts "Yay!"