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 要往前走。直到找到 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 所有测试案例

更新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]))
                {
                    dictionary.Add(nums[i], 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(日):【极速开发】第八梯次(中国台北)

想收到第一手公开培训课程资讯,或想询问企业内训、顾问、教练、咨询服务的,请洽 Facebook 粉丝专页:91敏捷开发之路。