LeetCode 的第 1 题 "Two Sum"，题目描述如下。

LeetCode 第一题题目解释：给一整数数组 nums 与一整数 target，假设刚好有一对 `nums[i] + nums[j] == target`，回传 int[]{ i, j }

## Step 1, 新增失败测试案例，Test_nums_is_1_8_and_target_is_9_should_return_0_1

``````        [TestMethod]
public void Test_nums_is_1_8_and_target_is_9_should_return_0_1()
{
var sut = new Solution();
var nums = new int[] { 1, 8 };
var target = 9;

var expected = new int[] { 0, 1 };

var actual = sut.TwoSum(nums, target);

CollectionAssert.AreEqual(expected, actual);
}``````

hard-code 以通过测试的生产代码：

``````    public class Solution
{
public int[] TwoSum(int[] nums, int target)
{
return new int[] { 0, 1 };
}
}``````

## Step 2, 重构测试程序，撷取出 TwoSum() 与 ShouldEqual() 两个方法

``````    [TestClass]
public class UnitTest1
{
[TestMethod]
public void Test_nums_is_1_8_and_target_is_9_should_return_0_1()
{
var nums = new int[] { 1, 8 };
var actual = TwoSum(nums, 9);

var expected = new int[] { 0, 1 };
ShouldEqual(expected, actual);
}

private static int[] TwoSum(int[] nums, int target)
{
var actual = new Solution().TwoSum(nums, target);
return actual;
}

private static void ShouldEqual(int[] expected, int[] actual)
{
CollectionAssert.AreEqual(expected, actual);
}
}``````

## Step 3, 新增失败测试案例，Test_nums_is_1_2_4_and_target_is_5_should_return_0_2

``````        [TestMethod]
public void Test_nums_is_1_2_4_and_target_is_5_should_return_0_2()
{
var nums = new int[] {1, 2, 4};
var actual = TwoSum(nums, 5);

var expected = new int[] {0, 2};
ShouldEqual(expected, actual);
}``````

## Step 5, 重构算法，先排序，以减少第二层循环巡览次数

``````        public int[] TwoSum(int[] nums, int target)
{
var sorted = nums
.Select((x, index) => Tuple.Create(x, index))
.OrderBy(x => x.Item1).ToArray();

for (int i = 0; i < sorted.Length; i++)
{
for (int j = i + 1; j < sorted.Length; j++)
{
var twoSum = sorted[i].Item1 + sorted[j].Item1;
if (twoSum == target)
{
return new int[] { Math.Min(sorted[i].Item2, sorted[j].Item2), Math.Max(sorted[i].Item2, sorted[j].Item2) };
}

if (twoSum > target)
{
break;
}
}
}

return null;
}``````

## Step 6, 重构算法，不用两层循环

``````        public int[] TwoSum(int[] nums, int target)
{
var sorted = nums
.Select((x, index) => Tuple.Create(x, index))
.OrderBy(x => x.Item1).ToArray();

var start = 0;
var end = sorted.Length - 1;
while (start < end)
{
if (sorted[start].Item1 + sorted[end].Item1 == target)
{
return new int[] { Math.Min(sorted[start].Item2, sorted[end].Item2), Math.Max(sorted[start].Item2, sorted[end].Item2) };
}
else if (sorted[start].Item1 + sorted[end].Item1 < target)
{
start++;
}
else
{
end--;
}
}

return null;
}``````

## 更新1: 改以 Dictionary 存放巡览过的值，只需一次循环

``````        public int[] TwoSum(int[] nums, int target)
{
var dictionary = new Dictionary();
for (int i = 0; i < nums.Length; i++)
{
var key = target - nums[i];
if (dictionary.ContainsKey(key))
{
return new int[] { dictionary[key], i };
}
else if (!dictionary.ContainsKey(nums[i]))
{
}
}

return null;
}``````

## Reference

GitHub commit history: LeetCode_1_two_sum

1. 2019/7/27(六)~2019/7/28(日)：演化式设计：测试驱动开发与持续重构 第六梯次（中国台北）
2. 2019/8/16(五)~2019/8/18(日)：【C#进阶设计-从重构学会高易用性与高弹性API设计】第二梯次（中国台北）
3. 2019/9/21(六)~2019/9/22(日)：Clean Coder：DI 与 AOP 进阶实战 第二梯次（中国台北）
4. 2019/10/19(六)：【针对遗留代码加入单元测试的艺术】第七梯次（中国台北）
5. 2019/10/20(日)：【极速开发】第八梯次（中国台北）