LeetCode 15. 3Sum
題目描述
題目解釋：給定一個整數陣列 S，找出裡面 3 個 element 相加為 0 的所有組合。
Step 1: 新增最單純的測試用例，三個 element 相加剛好為 0，test_nums_0_0_0
測試代碼：（含重構 assertion 的部分）
private static void ShouldBeEqual(int[] nums, List<List<int>> expected)
{
var actual = new Solution().ThreeSum(nums);
expected.ToExpectedObject().ShouldEqual(actual);
}
[TestMethod]
public void test_nums_0_0_0()
{
var nums = new int[] { 0, 0, 0 };
var expected = new List<List<int>>
{new List<int>() {0, 0, 0}};
ShouldBeEqual(nums, expected);
}
生產代碼：
public class Solution
{
public IList<IList<int>> ThreeSum(int[] nums)
{
return null;
}
}
Step 2: 使用 3 個 for loop 通過測試
生產代碼：
以3層迴圈通過測試用例
Step 3: 新增測試用例，test_nums_m1_m2_0_3
測試用例代表性：陣列有 4 個元素，存在一組唯一解，{-1, -2, 3}。
新增測試代碼：
生產代碼：加入判斷 item1 + item2 + item3 是否為 0，為 0 才符合需求。
生產代碼迭代差異
Step 4: 使用 HashSet<IList<int>> 排除相同 3 個 element 的重複組合解
生產代碼: 改用 HashSet<IList<int>> 取代 原本的 List<IList<int>>
改用 HashSet
自訂的
ListComparer 如下，覆寫 Equals() 強制排序後做比較：
自訂 ListComparer
Step 5: 優化演算法，先排序，加 condition 減少巡覽次數
生產代碼：因為需求是三個數字相加等於 0，所以排序後，只要三個數字相加大於 0 就可以終止巡覽。而前兩個數字相加若大於 0 也可以終止巡覽，因為後面的數字只會更大。
排序，增加 break 判斷式
Step 6: 重構，針對第一層迴圈，若 element 值 > 0 則終止巡覽。
生產代碼：增加第一層迴圈 break 條件。
增加第一層迴圈 break 條件
Step 7: 重構，針對當前數字如果與上一個巡覽數字相同，則略過此次巡覽，因為結果會跟上次一樣。
生產代碼：增加 continue 迴圈的條件。
public class Solution
{
public IList<IList<int>> ThreeSum(int[] oNums)
{
var nums = oNums.OrderBy(x => x).ToArray();
var set = new HashSet<IList<int>>(new ListComparer());
for (int i = 0; i < nums.Length; i++)
{
var item1 = nums[i];
if (item1 > 0)
{
break;
}
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
for (int j = i + 1; j < nums.Length; j++)
{
var item2 = nums[j];
if (item1 + item2 > 0)
{
break;
}
if (j > i + 1 && nums[j] == nums[j - 1])
{
continue;
}
for (int k = j + 1; k < nums.Length; k++)
{
var item3 = nums[k];
var threeSum = item1 + item2 + item3;
if (threeSum > 0)
{
break;
}
if (k > j + 1 && nums[k] == nums[k - 1])
{
continue;
}
if (threeSum == 0)
{
set.Add(new List<int> { item1, item2, item3 });
}
}
}
}
return set.ToList();
}
}
Step 8: 重構，把 HashSet 換回 List，因為已經排序+判斷是否與上一次數字相同，不會存在重複的組合解
生產代碼：
改回 List 以避免不必要的判斷
Step 9: 重構，減少第一層迴圈巡覽數量
生產代碼：第一層迴圈只需巡覽到倒數第三個 element，因為最後兩個在第二跟第三個迴圈會拿來用。
調整第一層迴圈長度
Step 10: 重新調整演算法，用 start, end 旗標取代第二、第三層迴圈
生產代碼：第二層迴圈，設定一個 start 旗標由起點的 element index 開始，一個 end 旗標由最後一個 element index 開始，面對面逼近。
如果
num1 + num[start] + num[end] > 0，代表end要再小一點。如果小於 0 代表start要再大一點。
public class Solution
{
public IList<IList<int>> ThreeSum(int[] oNums)
{
var nums = oNums.OrderBy(x => x).ToArray();
var set = new List<IList<int>>();
for (int i = 0; i < nums.Length - 2; i++)
{
var item1 = nums[i];
if (item1 > 0)
{
break;
}
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
var start = i + 1;
var end = nums.Length - 1;
while (start < end)
{
if (start > i + 1 && nums[start] == nums[start - 1])
{
start++;
continue;
}
if (end < nums.Length - 1 && nums[end] == nums[end + 1])
{
end--;
continue;
}
var threeSum = nums[start] + nums[end] + item1;
if (threeSum == 0)
{
set.Add(new List<int>() { item1, nums[start], nums[end] });
end--;
}
else if (threeSum > 0)
{
end--;
}
else
{
start++;
}
}
}
return set;
}
}
Step 11: 重構，重新命名與加入 break 判斷式，最終版本生產代碼
生產代碼：
public class Solution
{
public IList<IList<int>> ThreeSum(int[] oNums)
{
var nums = oNums.OrderBy(x => x).ToArray();
var set = new List<IList<int>>();
for (int i = 0; i < nums.Length - 2; i++)
{
var a = nums[i];
if (a > 0)
{
break;
}
if (i > 0 && a == nums[i - 1])
{
continue;
}
var start = i + 1;
var end = nums.Length - 1;
while (start < end)
{
var b = nums[start];
if (a + b > 0)
{
break;
}
if (start > i + 1 && b == nums[start - 1])
{
start++;
continue;
}
var c = nums[end];
if (end < nums.Length - 1 && c == nums[end + 1])
{
end--;
continue;
}
var threeSum = a + b + c;
if (threeSum == 0)
{
set.Add(new List<int>() { a, b, c });
end--;
}
else if (threeSum > 0)
{
end--;
}
else
{
start++;
}
}
}
return set;
}
}
通過 LeetCode 上所有測試用例
通過 LeetCode 所有測試用例
結論
不少的調整過程，最後大半的演算法重寫，但仍可以看到，原先版本的思路與代碼片段仍保留著其精髓。這也是 TDD 比較輕鬆的地方，你可以用最快的速度完成滿足需求的生產代碼，有餘力時重構調整，那怕是整骨型的演算法重寫，你的思路也不需要重來，你前面花力氣寫的測試用例不會白費。
更何況，最大的差異在於「化繁為簡」跟「敏捷式的儘早交付」，沒有 TDD 很容易就想一步登天，邊調邊錯，更糟糕的是調了不知道有錯。有 TDD 就是每跨出一步都是比較輕鬆的，你知道你要走的路有哪一些，而現在走到哪裡。
GitHub Commit History: LeetCode_15_3Sum
