## Step 1: 新增最單純的測試案例，三個 element 相加剛好為 0，test_nums_0_0_0

        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 7: 重構，針對當前數字如果與上一個巡覽數字相同，則略過此次巡覽，因為結果會跟上次一樣。

    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 10: 重新調整演算法，用 start, end 旗標取代第二、第三層迴圈

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

## 結論

GitHub Commit History: LeetCode_15_3Sum
 想收到第一手公開培訓課程資訊，或想詢問企業內訓、顧問、教練、諮詢服務的，請加 Odd-e Line 帳號。