是 Two Sum 的一種另類進階，要從 nums 中找出和為 0 的三個 element ，由於答案可能有多種，故答案會是個 List of list 。特別注意，題目中有提到不能有兩個內容一樣的 list，故要做去重處理。 也因為題目解答並沒有對 nums 的 index 有任何要求，故可以把 nums 排序，為解題拓開另一種思路。

多指針解法

本題使用多指針法是最優的解，可進一步減少空間複雜度。若參考 Two Sum 使用 hash-table ，空間複雜度會比較高。

思路

比較優的解法的使用重點，是想到可以對原 nums 進行排序，這樣對指針的移動就會清楚很多。那指針該如何移動呢？ 首先是先固定一個指針 i，相對位置如圖例：

nums = [-4, -1, -1, 0, 1, 2]
        i   j              k
  • 三數和小於 0，則將左邊那個指針 j 右移，使得三數和增大一些。
  • 三數和大於 0，則將右邊那個指針 k 左移，使得三數和變小一些。
  • 三數和等於 0，為答案之一，要記錄下來。

這裡也可以注意，i 不用遍歷到最後一個，而是到倒數第三個就可以了(因為是 3 sum)。

另外題目有特別提到，must not contain duplicate triplets，故需要思考一下遇到「重複的 triplets」該怎麼辦呢 ? 常見的處理方式是 「while 跳過」或者是 「使用 set 儲存」，選用 「while 跳過」會好一些，空間複雜度比較優。

再來可以加個 if(nums[i] == 0) break; 判斷來優化。因為把 nums 進行由小到大排序了，所以若是nums[i] == 0，代表之後的元素都大於等於零，又因為三數大於零的數加起來，基本一定大於等於零，故可以直接 break，省略許多判斷。

解答

class Solution {
	public List<List<Integer>> threeSum( int[] nums ) {
		Arrays.sort( nums );
		List<List<Integer>> ans = new ArrayList<>();
		for ( int i = 0; i < nums.length - 2; i++ ) {
			int j = i + 1;
			int k = nums.length - 1;

            if (nums[i] > 0){
                break;
            }

			while (j < k) {
				if ( nums[i] + nums[j] + nums[k] == 0 ) {
					List<Integer> list = List.of( nums[i], nums[j], nums[k] );
					ans.add( list );
					if ( nums[i] == 0 ) {
						break;
					}
					while (j < k && nums[j] == nums[j + 1]) j++;
					while (j < k && nums[k] == nums[k - 1]) k--;
					j++;
					k--;
				} else if ( nums[i] + nums[j] + nums[k] > 0 ) {
					k--;
				} else {
					j++;
				}
			}
			while (i < k && nums[i] == nums[i + 1]) i++;
		}
		return ans;
	}
}

題目的條件有 -10^5 <= nums[i] <= 10^5，故三數和不會超過Integer.MAX_VALUE。因為這個條件所以不用擔心數字相加會發生甚麼問題~

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()

        n = len(nums)
        ans = []
        for i in range(n-2):

            if i > 0 and nums[i] == nums[i-1]:
                continue

            if nums[i] > 0:
                break

            j = i + 1
            k = n - 1
            while j < k :

                s = nums[i] + nums[j] + nums[k]

                if s == 0:
                    ans.append([nums[i], nums[j], nums[k]])
                    j +=1
                    k -=1

                    while j < k and nums[j] == nums[j-1]:
                        j += 1

                    while k > j and nums[k] == nums[k+1]:
                        k -= 1

                elif s < 0:
                    j +=1
                    while j < k and nums[j] == nums[j-1]:
                        j += 1
                else:
                    k -=1
                    while k > j and nums[k] == nums[k+1]:
                        k -= 1

        return ans

Java 和 Python 分別在「指針移動之前」和「指針移動之後」，兩個不同時候，做去除重複項動作。可以注意一下細微差異

時間空間複雜度

時間複雜度: O(N^2)
  • 排序的時間複雜度為 O(NlogN)
  • for loop 遍歷 nums，且內部有一個 while loop 再遍歷 nums，是 O(N^2)
空間複雜度：O(1)

演算法過程只需要存儲 i, j, k ，花費O(1)空間而已。

也可是參考Two Sum 使用 hash-table 來解題，空間複雜度會比較高: O(n)

解答

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()

        res = set()
        n = len(nums)
        for i in range(n - 2):

            if i > 0 and nums[i] == nums[i-1]:
                continue

            seen = set()
            for j in range(i+1, n):

                target = -nums[i] - nums[j]

                if target in seen:
                    res.add((nums[i], target, nums[j]))
                else:
                    seen.add(nums[j])

        return [list(t) for t in res]

  • seen = set() 作為 hash-table ，記錄「掃過的數字」nums[j]，要放在尋找 target 迴圈的外面
  • 還要特別處理重複的答案，這邊使用的手法是：
    • res 使用 set() 用來避免重複的 triplets
    • 由於 cannot use 'list' as a set element (unhashable type: 'list')，所以 res 要使用 res.add((nums[i], target, nums[j]))，代表 set 內是加入 tuple`()` 而不能是 list`[]`
  • 最後把 tuple 轉為答案所需的 list: [list(t) for t in res]

參考資料