題目

https://leetcode.com/problems/3sum/

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解答

C#

public class Solution {
    IList<IList<int>> ThreeSum(int[] nums) 
    {
        List<IList<int>> result = new List<IList<int>>();
        List<int> temp;

        Array.Sort(nums);
        for (int first = 0; first < nums.Length - 2; first++)
        {
            // The numbers of first, second, third should be indexes.
            if (first > 0 && nums[first] == nums[first-1])
            {
                continue;
            }
            int second = first + 1;
            int third = nums.Length - 1;
            while (second < third)
            {
                if (nums[second] == nums[second - 1] && second > first +1)
                {
                    second++;
                    continue;
                }
                int sum = nums[first] + nums[second] + nums[third];
                if (sum == 0)
                {
                    temp = new List<int>
                    {
                        nums[first],
                        nums[second],
                        nums[third]
                    };
                    result.Add(temp);
                    second++;
                    third--;
                }
                else if (sum < 0)
                {
                    second++;
                }
                else
                {
                    third--;
                }
            }
        }
        return result;
    }
}

結果

Runtime: 308 ms, faster than 98.73% of C# online submissions.

Memory Usage: 34.8 MB, less than 15.0% of C# online submissions.

Time Complexity: O(n^2)

Space Complextiy: O(n)~O(n^2)

為什麼我要這樣做？

本來一開始我是使用暴力法 ── 用3個for迴圈去解決，但是這樣不僅是 O(n^3)
LeetCode 也不給我過 所以改成兩個迴圈的寫法

1. 將 array 從小到大升冪排序
2. 將須要找出的3個數的 index 分別表示為 first , second , third
3. 用 for 迴圈計算，並將 first 做為 nums 的起始點
4. second 則為 first + 1 為起始點
5. third 則為 nums.Length - 1 為起始點
6. 並判斷 nums[first] + nums[second] + nums[third] 是否為 0
   • 若等於 0，則為解答之一，Add 到 List
   • 若小於 0，則代表負數太大，需要將 second 移至下一個較小的負數 (second++)
   • 若大於 0，則代表正數太大，需要將 third 移至上一個較小的正數 (third--)
7. 另外判斷 first 是否已經重複，若重複則跳過此次迴圈，因為答案也會是一樣的
   • 如 {-1, -1, 0, 1, 2}
8. 另外判斷 second 是否已經重複，若重複則 second++，並跳過此次迴圈，因為答案也會是一樣的
   • 如 {-4, 2, 2, 2, 3}

7. 與 8. 是讓效能再更好的其中之一條件，不用重複查找已經查找過的數字。 若沒有寫也是會過的哦！

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以 array int[] nums = {-1, 0, 1, 2, -1, -4} 為例

sum = (-4) + (-1) + 2 = -3
sum < 0，second ++

second 與上次相同，second ++

sum = (-4) + 0 + 2 = -2
sum < 0，second ++

sum = (-4) + 1 + 2 = -1
sum < 0，second ++
second == third，回到最新一輪，first++

sum = (-1) + (-1) + 2 = 0，Add to List
second++
third--

sum = (-1) + 0 + 1 = 0，Add to List
second++
third--
second > third，回到最新一輪，first++

first 與上次相同，回到最新一輪，first++

sum = 0 + 1 + 2 = 3

結束查找並 return List<List<int>> ({-1, -1, 2}, {-1, 0, 1})。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉