LeetCode 15. 3Sum

LeetCode 第 15 題: 3 Sum

題目解釋:給定一個整數陣列 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 通過測試

生產代碼:

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>> 

自訂的 ListComparer 如下,覆寫 Equals() 強制排序後做比較:

Step 5: 優化演算法,先排序,加 condition 減少巡覽次數

生產代碼:因為需求是三個數字相加等於 0,所以排序後,只要三個數字相加大於 0 就可以終止巡覽。而前兩個數字相加若大於 0 也可以終止巡覽,因為後面的數字只會更大。

Step 6: 重構,針對第一層迴圈,若 element > 0 則終止巡覽。

生產代碼:增加第一層迴圈 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,因為已經排序+判斷是否與上一次數字相同,不會存在重複的組合解

生產代碼:

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 上所有測試案例

結論

不少的調整過程,最後大半的演算法重寫,但仍可以看到,原先版本的思路與代碼片段仍保留著其精髓。這也是 TDD 比較輕鬆的地方,你可以用最快的速度完成滿足需求的生產代碼,有餘力時重構調整,那怕是整骨型的演算法重寫,你的思路也不需要重來,你前面花力氣寫的測試案例不會白費。

更何況,最大的差異在於「化繁為簡」跟「敏捷式的儘早交付」,沒有 TDD 很容易就想一步登天,邊調邊錯,更糟糕的是調了不知道有錯。有 TDD 就是每跨出一步都是比較輕鬆的,你知道你要走的路有哪一些,而現在走到哪裡。
GitHub Commit History: LeetCode_15_3Sum 

blog 與課程更新內容,請前往新站位置:http://tdd.best/