LeetCode 1. Two Sum

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

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

測試用例代表性：最單純的情境，nums 長度為 2，結果為 {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

測試用例代表性：nums 長度為 3，符合條件的結果為 {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 4, 使用雙層迴圈直接找到 nums[i] + nums[j] == target 的組合

第二層迴圈 index 從 i + 1 開始

生產代碼差異：

生產代碼迭代差異

到這邊就滿足所有功能性的需求，但演算法的效率是最差的。

Step 5, 重構演算法，先排序，以減少第二層迴圈巡覽次數

原需求為找到 nums[i] + nums[j] == target，當先排序之後（OrderBy 默認為 quick sort），第二層迴圈如果出現 nums[i] + nums[j] > target 時，代表第二層迴圈不用比了，該回到第一個迴圈繼續往後巡覽。

生產代碼如下：

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

到這邊已經能通過 LeetCode 的所有測試案例。

Step 6, 重構演算法，不用兩層迴圈

要找到 nums[i] + nums[j] == target，可以針對原本的 nums 集合排序後，設定 start 與 end 兩個 index flag，若 nums[start] + nums[end] > target，代表 end flag 要往回退。若 nums[start] + nums[end] < target 則代表 start flag 要往前走。直到找到 nums[i] + nums[j] == target 為止。

生產代碼：

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

通過 LeetCode 所有測試用例

通過 LeetCode 所有測試用例

更新1: 改以 Dictionary<int, int> 存放巡覽過的值，只需一次迴圈

生產代碼：

        public int[] TwoSum(int[] nums, int target)
        {
            var dictionary = new Dictionary<int, int>();
            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]))
                {
                    dictionary.Add(nums[i], i);
                }
            }

            return null;
        }

更新後的速度

Reference

GitHub commit history: LeetCode_1_two_sum