【LeetCode】15. 3Sum 解題報告

15. 3Sum / Medium

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

Solution: Three Pointers

思路

這題基本上是 Two sum 的變體,其實只要固定一個數就變成 Two Sum 了。
因為求的不是 index 而是數字集合,所以我們可以先排序。

首先嘗試暴力解,需要三個迴圈,會超時,所以我們需要減少搜索空間。

一個迴圈固定一個數,迴圈兩個指標左右包夾剩下的區域,因為有排序過,所以如果目前指標計算出來的值小於 0,代表負數比較大,左邊的指標要右移,反之則是正數比較大,右邊的指標要左移。

找到解的時候,因為結果必須是不重複的,我們可以直接迴圈略過鄰近相同的數。

效能

Complexity

  • Time Complexity: O(N^2)
  • Space Complexity: O(N^2)

LeetCode Result

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
if(n < 3) return vector<vector<int>>(0);
vector<vector<int>> ans(0);
sort(nums.begin(), nums.end());

if(nums[0] > 0) return ans;
for(int i = 0; i < n-2; ++i) {
int left = i+1, right = n-1;
while(i < n-2 && nums[i] == nums[i+1]) ++i;
while(left < right) {
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0) {
ans.emplace_back(vector<int>{nums[i], nums[left], nums[right]});
while(left < right && nums[left] == nums[left+1]) ++left;
while(left < right && nums[right] == nums[right-1]) --right;
if(left == right) break;
++left;
--right;
} else if (sum < 0) {
++left;
} else {
--right;
}
}
}
return ans;
}
};