Skip to content

Latest commit

 

History

History
75 lines (63 loc) · 3.09 KB

README.md

File metadata and controls

75 lines (63 loc) · 3.09 KB

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:

Solution 1.

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;
    }
};