1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
<<-DOC
You have two integer arrays, a and b, and an integer target value v.
Determine whether there is a pair of numbers, where one number is taken from a and the other from b, that can be added together to get a sum of v.
Return true if such a pair exists, otherwise return false.
Example
For a = [1, 2, 3], b = [10, 20, 30, 40], and v = 42, the output should be
sumOfTwo(a, b, v) = true.
Input/Output
[time limit] 4000ms (rb)
[input] array.integer a
An array of integers.
Guaranteed constraints:
0 ≤ a.length ≤ 105,
-109 ≤ a[i] ≤ 109.
[input] array.integer b
An array of integers.
Guaranteed constraints:
0 ≤ b.length ≤ 105,
-109 ≤ b[i] ≤ 109.
[input] integer v
Guaranteed constraints:
-109 ≤ v ≤ 109.
[output] boolean
true if there are two elements from a and b which add up to v, and false otherwise.
DOC
describe "sum_of_two" do
# time: nlogn
def sum_of_two(a, b, v)
outer, inner = a.size > b.size ? [b.sort, a.sort] : [a.sort, b.sort]
outer.any? { |i| inner.bsearch { |x| (v - i) <=> x } }
end
# time: n
def sum_of_two(a, b, v)
hash = {}
a.each { |x| hash[x] = true }
b.any? { |x| hash[v - x] }
end
def sum_of_two(a, b, v)
(a.map { |x| v - x } & b).size > 0
end
[
{ a: [1, 2, 3], b: [10, 20, 30, 40], v: 42, expected: true },
{ a: [1, 2, 3], b: [10, 20, 30, 40], v: 50, expected: false },
{ a: [], b: [1, 2, 3, 4], v: 4, expected: false },
{ a: [10, 1, 5, 3, 8], b: [100, 6, 3, 1, 5], v: 4, expected: true },
{ a: [1, 4, 3, 6, 10, 1, 0, 1, 6, 5], b: [9, 5, 6, 9, 0, 1, 2, 1, 6, 10], v: 8, expected: true },
{ a: [3, 2, 3, 7, 5, 0, 3, 0, 4, 2], b: [6, 8, 2, 9, 7, 10, 3, 8, 6, 0], v: 2, expected: true },
{ a: [4, 6, 4, 2, 9, 6, 6, 2, 9, 2], b: [3, 4, 5, 1, 4, 10, 9, 9, 6, 4], v: 5, expected: true },
{ a: [6, 10, 25, 13, 20, 21, 11, 10, 18, 21], b: [21, 10, 6, 0, 29, 25, 1, 17, 19, 25], v: 37, expected: true },
{ a: [22, 26, 6, 22, 17, 11, 9, 22, 7, 12], b: [14, 25, 22, 27, 22, 30, 6, 26, 30, 27], v: 56, expected: true },
{ a: [17, 72, 18, 72, 73, 15, 83, 90, 8, 18], b: [100, 27, 33, 51, 2, 71, 76, 19, 16, 43], v: 37, expected: true },
].each do |x|
it do
expect(sum_of_two(x[:a], x[:b], x[:v])).to eql(x[:expected])
end
end
end
|
