### [TDD] leet code 219. Contains Duplicate II

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 absolute difference between i and j is at most k.

    [TestClass]
public class UnitTest1
{
[TestMethod]
public void Test_k_is_zero_should_return_false()
{
var nums = new int[] { 1, 2, 3, 1, 2 };
var k = 0;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}
}

    public static class Solution
{
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
throw new NotImplementedException();
}
}

        public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;

throw new NotImplementedException();
}

        [TestMethod]
public void Test_nums_5_5_and_k_is_1_should_return_true()
{
var nums = new int[] { 5, 5 };
var k = 1;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}

        public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;

var set = new HashSet<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!set.Add(nums[i])) return true;
}

throw new NotImplementedException();
}

        [TestMethod]
public void Test_nums_5_6_and_k_is_1_should_return_false()
{
var nums = new int[] { 5, 6 };
var k = 1;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}

        public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;

var set = new HashSet<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!set.Add(nums[i])) return true;
}

return false;
}

        [TestMethod]
public void Test_nums_5_6_5_and_k_is_1_should_return_false()
{
var nums = new int[] { 5, 6, 5 };
var k = 1;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}

        public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;

var windowSize = k + 1;
for (int i = 0; i < nums.Length; i++)
{
var windowNums = nums.Skip(i).Take(windowSize);
var set = new HashSet<int>();
foreach (var windowNum in windowNums)
{
if (!set.Add(windowNum)) return true;
}
}

return false;
}

        [TestMethod]
public void Test_nums_5_6_5_and_k_is_2_should_return_true()
{
var nums = new int[] { 5, 6, 5 };
var k = 2;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}

        public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;

var set = new HashSet<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!set.Add(nums[i])) return true;

//keep only 1 window sliding, remove int just out of window
if (i >= k) set.Remove(nums[i - k]);
}

return false;
}

## 結論

• 拿 leet code 來練 TDD 挺過癮的
• leet code 通常都會針對演算法而有效能限制，而優化演算法效能的部分，很難從 TDD 來驅動優化的設計過程

但這並非代表 TDD 無用，因為在一開始使用 TDD 透過一個一個代表關鍵商業邏輯的測試案例，來一步步堆砌成滿足需求的產品程式碼，是很有幫助的。在這個過程中，會一步步釐清自己的想法與需求的複雜性。

到最後如果需要對效能或演算法進行優化，不論是判斷式或迴圈的搬移、合併、調整，甚至整個演算法重寫，透過版本控管的保護，你隨時可以還原到可運作的版本。透過先前完整的關鍵商業邏輯測試案例保護，你不必擔心優化或重寫演算法的過程中，漏了什麼特別的需求
• TDD 是種修煉，也是種習慣的養成。當你茫然毫無頭緒，想理頭緒時，TDD 讓你很容易下手TDD 可以讓你先求有，再求好

using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Collections.Generic;

namespace ContainsDuplicateII
{
[TestClass]
public class UnitTest1
{
[TestMethod]
public void Test_k_is_zero_should_return_false()
{
var nums = new int[] { 1, 2, 3, 1, 2 };
var k = 0;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}

[TestMethod]
public void Test_nums_5_5_and_k_is_1_should_return_true()
{
var nums = new int[] { 5, 5 };
var k = 1;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}

[TestMethod]
public void Test_nums_5_6_and_k_is_1_should_return_false()
{
var nums = new int[] { 5, 6 };
var k = 1;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}

[TestMethod]
public void Test_nums_5_6_5_and_k_is_1_should_return_false()
{
var nums = new int[] { 5, 6, 5 };
var k = 1;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}

[TestMethod]
public void Test_nums_5_6_5_and_k_is_2_should_return_true()
{
var nums = new int[] { 5, 6, 5 };
var k = 2;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}

[TestMethod]
public void Test_nums_1_2_3_2_1_k_is_2_should_return_true()
{
var nums = new int[] { 1, 2, 3, 2, 1 };
var k = 2;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}

[TestMethod]
public void Test_nums_1_2_3_1_2_k_is_2_should_return_false()
{
var nums = new int[] { 1, 2, 3, 1, 2 };
var k = 2;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}

[TestMethod]
public void Test_nums_9_5_6_9_4_4_9_and_k_is_3_should_return_true()
{
var nums = new int[] { 9, 5, 6, 4, 9, 4, 4, 9 };
var k = 3;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}
}

public static class Solution
{
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;

var set = new HashSet<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!set.Add(nums[i])) return true;

//keep only 1 window sliding, remove int just out of window
if (i >= k) set.Remove(nums[i - k]);
}

return false;
}
}
}