//LeetCode Easy 219 Contains Duplicate II
// Question:
//Given an array of integers and an integer k, find out whether there are two distinct indices i
//and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
//It is supposed to give me true, but it gives me false.
//Any help, I appreciate it. Thank you so much.
class Solution
{
func containsNearbyDuplicate (nums: [Int], _ k: Int) ->Bool
{
var dict = [Int:Int]()
for i in 0..<nums.count
{
if dict[nums[i]] != nil
{
if dict.values.contains(nums[i]) && (i - dict[nums[i]]! <= k)
{
return true
}
else
{
dict[i] = nums[i]
}
}
}
return false
}
}
let test1 = Solution()
//var haha = [1,2,1,5,6,7,6,8,7,5]
//var haha = [1]
// var haha = [1,2]
// var haha = [1,2,3,5,6,8]
var haha = [-1,-1]
var result = test1.containsNearbyDuplicate(haha,1)
print(result)LeetCode: Contains Duplicate II , it can't pass[-1,-1]
Why such a complex code, what is the need for dict ? In addition, dict is not initailized when you perform the test.
If I understand what you want to do :
class Solution {
func containsNearbyDuplicate (nums: [Int], _ k: Int) ->Bool {
print(nums)
for i in 0..<nums.count {
for j in i+1..<nums.count {
if (abs(nums[i] - nums[j]) <= k) {
return true
}
}
}
return false
}
}
let test1 = Solution()
var haha = [-1,-1]
var result = test1.containsNearbyDuplicate(haha,1) // true
var haha2 = [-1,1]
var result2 = test1.containsNearbyDuplicate(haha2,1) // falseOK, I misread your intent.
I would do this :
class Solution {
func containsNearbyDuplicate (nums: [Int], _ k: Int) ->Bool {
if k < 0 { return false }
for i in 0..<nums.count {
let iMax = min(nums.count, i+k+1)
for j in i+1..<iMax {
if nums[i] == nums[j] {
return true
}
}
}
return false
}
}
let test1 = Solution()
var haha = [1,2,1,5,6,7,6,8,7,5]
var result = test1.containsNearbyDuplicate(haha,1) // false
var haha2 = [-1,-1]
var result2 = test1.containsNearbyDuplicate(haha2,1) // trueThank so such for yout help! Since I need to care about time complexity, so I use dictionary to try to decrease time.
Thank so such for yout help! Since I need to care about time complexity, so I can not use two For loop. Someone else helped me out. I will share the solution.
class Solution {
func containsNearbyDuplicate (nums: [Int], _ k: Int) ->Bool {
var dict = [Int:Int]()
for i in 0..<nums.count {
if let firstIndex = dict[nums[i]] where i - firstIndex <= k {
return true
}
dict[nums[i]] = i
}
return false
}
}This is solution from Stackoverflow. Someone just helped me out.
Beyond code readability, if performance is an issue, do compare the 2 algorithms.
I tested on haha = [1,2,1,5,6,7,6,8,7,5], for 100 000 iterations.
With dict: time elapsed around 7s
With double loop, less than 1 s.