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-105 <= nums[i] <= 105
Companies:
Amazon, Facebook, Microsoft, Apple, Bloomberg, Uber, Google, Yahoo, VMware, Walmart Labs, Cisco, Rubrik, Salesforce, eBay, Adobe
Related Topics:
Array, Two Pointers
Similar Questions:
Sort the array in ascending order.
Pin the first number as A[i]. For the other two numbers, we can use two pointers to scan A[(i+1)..(N-1)], one from i+1 rightward, one from N-1 leftward.
// OJ: https://leetcode.com/problems/3sum/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& A) {
sort(begin(A), end(A));
vector<vector<int>> ans;
int N = A.size();
for (int i = 0; i < N - 2; ++i) {
if (i && A[i] == A[i - 1]) continue;
int L = i + 1, R = N - 1;
while (L < R) {
int sum = A[i] + A[L] + A[R];
if (sum == 0) ans.push_back({ A[i], A[L], A[R] });
if (sum >= 0) {
--R;
while (L < R && A[R] == A[R + 1]) --R;
}
if (sum <= 0) {
++L;
while (L < R && A[L] == A[L - 1]) ++L;
}
}
}
return ans;
}
};