Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 339
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Given an array of numbers and a number k, determine if there are three entries in the array which add up to the specified number k. For example, given `[20, 303, 3, 4, 25]` and `k = 49`, return true as `20 + 4 + 25 = 49`.

Pull request description:
Day339
Resolves #676.

Patch:
diff --git a/README.md b/README.md
index d5171eb..c4ca6c1 100644
--- a/README.md
+++ b/README.md
@@ -329,3 +329,4 @@ problems from
 * [Day 323](https://github.com/vaskoz/dailycodingproblem-go/issues/656)
 * [Day 324](https://github.com/vaskoz/dailycodingproblem-go/issues/658)
 * [Day 325](https://github.com/vaskoz/dailycodingproblem-go/issues/660)
+* [Day 339](https://github.com/vaskoz/dailycodingproblem-go/issues/676)
diff --git a/day339/problem.go b/day339/problem.go
new file mode 100644
index 0000000..1b69736
--- /dev/null
+++ b/day339/problem.go
@@ -0,0 +1,29 @@
+package day339
+
+// ThreeSum returns the first possible answer to the 3-SUM
+// problem.
+// Runs in O(N^2) time and O(N) space due to a map.
+// If no answer exists it returns nil.
+func ThreeSum(nums []int, k int) []int {
+	m := make(map[int]int)
+	for _, v := range nums {
+		m[v]++
+	}
+	for i := 0; i < len(nums)-2; i++ {
+		for j := i + 1; j < len(nums)-1; j++ {
+			needed := k - nums[i] - nums[j]
+			if m[needed] >= 0 {
+				m[nums[i]]--
+				m[nums[j]]--
+				m[needed]--
+				if m[nums[i]] >= 0 && m[nums[j]] >= 0 && m[needed] >= 0 {
+					return []int{nums[i], nums[j], needed}
+				}
+				m[nums[i]]++
+				m[nums[j]]++
+				m[needed]++
+			}
+		}
+	}
+	return nil
+}


Test patch:
diff --git a/day339/problem_test.go b/day339/problem_test.go
new file mode 100644
index 0000000..e187240
--- /dev/null
+++ b/day339/problem_test.go
@@ -0,0 +1,36 @@
+package day339
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	nums     []int
+	k        int
+	expected []int
+}{
+	{[]int{20, 303, 3, 4, 25}, 49, []int{20, 4, 25}},
+	{[]int{20, 303, 3, 4, 25}, 1000, nil},
+	{[]int{300}, 900, nil},
+	{[]int{300, 301, 300}, 900, nil},
+	{[]int{300, 300, 301}, 900, nil},
+}
+
+func TestThreeSum(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := ThreeSum(tc.nums, tc.k); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkThreeSum(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ThreeSum(tc.nums, tc.k)
+		}
+	}
+}