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
76
77
78
79
80
81
82
83
|
<<-DOC
Given an array of integers nums and an integer k,
determine whether there are two distinct indices i and j
in the array where nums[i] = nums[j] and the
absolute difference between i and j is less than or equal to k.
Example
For nums = [0, 1, 2, 3, 5, 2] and k = 3, the output should be
containsCloseNums(nums, k) = true.
There are two 2s in nums, and the absolute difference between their positions is exactly 3.
For nums = [0, 1, 2, 3, 5, 2] and k = 2, the output should be
containsCloseNums(nums, k) = false.
The absolute difference between the positions of the two 2s is 3, which is more than k.
Input/Output
[time limit] 4000ms (rb)
[input] array.integer nums
Guaranteed constraints:
0 ≤ nums.length ≤ 55000,
-231 - 1 ≤ nums[i] ≤ 231 - 1.
[input] integer k
Guaranteed constraints:
0 ≤ k ≤ 35000.
[output] boolean
DOC
describe "#contains_close_numbers" do
def diff(x)
1.upto(x.size - 1).map { |n| (x[n] - x[n-1]).abs }
end
def contains_close_numbers(numbers, k)
return numbers[0] == numbers[1] if numbers.size == 2
items = Hash.new { |hash, key| hash[key] = [] }
numbers.each_with_index do |number, index|
items[number].push(index)
return true if diff(items[number]).find { |x| x <= k }
end
false
end
def contains_close_numbers(numbers, k)
items = {}
numbers.each_with_index do |number, index|
puts items.inspect
return true if items[number] && (index - items[number]) <= k
items[number] = index
end
false
end
[
{ nums: [0, 1, 2, 3, 5, 2], k: 3, x: true },
{ nums: [0, 1, 2, 3, 5, 2], k: 2, x: false },
{ nums: [], k: 0, x: false },
{ nums: [99, 99], k: 2, x: true },
{ nums: [2, 2], k: 3, x: true },
{ nums: [1, 2], k: 2, x: false },
{ nums: [1, 2, 1], k: 2, x: true },
{ nums: [1, 0, 1, 1], k: 1, x: true },
{ nums: [1, 2, 1], k: 0, x: false },
{ nums: [1, 2, 1], k: 1, x: false },
{ nums: [1], k: 1, x: false },
{ nums: [-1, -1], k: 1, x: true },
{ nums: [1,2,3,4,1], k: 5, x: true },
].each do |x|
it do
expect(contains_close_numbers(x[:nums], x[:k])).to eql(x[:x])
end
end
end
|
