#15. 3Sum

題目描述

給你一個整數陣列nums，回傳所有的三數字組合[nums[i], nums[j], nums[k]]，其中i != j、i != k以及j != k，並且nums[i] + nums[j] + nums[k] == 0。

答案中不能有重複的組合。

限制條件

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

解題思路

Brute Force

暴力解就是窮盡每個組合。

public class Solution { 
	public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        var ans = new List<IList<int>>();
        var hs = new HashSet<(int,int,int)>();
        for(int i=0;i<nums.Length-2;i++){
            for(int j=i+1;j<nums.Length-1;j++){
                for(int k=j+1;k<nums.Length;k++){
                    if(nums[i]+nums[j]+nums[k]==0) hs.Add((nums[i],nums[j],nums[k]));
                }                
            }            
        }
        foreach(var tuple in hs){
            (int i,int j,int k) = tuple;
            ans.Add(new List<int>(){i,j,k});
        }
        return ans;
    }
}

複雜度分析：

時間複雜度：O(n^3)。
空間複雜度：O(m)，m為ans.Length。

Two Pointers

雖然有3個數字要決定，但是我們可以固定住其中一個，這樣就變成了Two Sum的問題，但與Two Sum不同的是，這裡的Two Sum有多種組合，因此要使用Two Pointer來測試不同的答案組合。

因為陣列沒有排序，因此我們要先整理陣列。

public class Solution { 
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        int start = 0;
        var ans = new List<IList<int>>();
        while(nums[start]<=0 && start<nums.Length-2){
            int left = start+1;
            int right = nums.Length-1;
            while(left<right){
                int sum = nums[start]*-1;
                if(nums[left]+nums[right]<sum){
                    left++;
                }else if(nums[left]+nums[right]>sum){
                    right--;
                }else{
                    ans.Add(new List<int>(){nums[start],nums[left],nums[right]});
                    int prev_left = nums[left];
                    while(nums[left]==prev_left && left<right) left++;
                    int prev_right = nums[right];
                    while(nums[right]==prev_right && left<right) right--; 
                }
            }
            int prev_start = nums[start];
            while(nums[start]==prev_start && start<nums.Length-2) start++;
        }
        return ans;
    }
}

複雜度分析：

時間複雜度：O(n^2)。
空間複雜度：O(m)，m為ans.Length。

學習重點

Sorting
Hash Set
Two Pointers