# 222. Count Complete Tree Nodes

Question link is here.

# Question

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: []

# Solution

# brute force

The simplest way to do this is using brute force to check all possiable combination. But that's not what we want to do.

# two pointer

We are asked to find any 3 tuple(a, b, c) that a + b + c == 0, so, we can convert this problem into find two numbers a,b in the array that there exists a c in the array so that a + b == -c. Therefore, we fix c, we can iterate through the array to find any a, b that satisfy this conditon.

To make finding a, b more efficient, we can use two pointers: left and right, so when nums[left] + nums[right] > -c, we reduce right, and when nums[left] + nums[right] < -c, we increase left. But we need to sort the array first so this two pointer method can be used.

And to remove duplicate, we just need to make sure we don't use the same c more than once. I.E. when nums[i] == nums[i-1], we skip this loop until nums[i] != nums[i-1].

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                continue;
            }
            if(i == 0 || nums[i] != nums[i-1]) {
                int left = i + 1;
                int right = nums.length - 1;
                while(left < right) {
                    int temp = nums[i] + nums[left] + nums[right];
                    if(temp == 0) {
                        res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        left += 1;
                        right -= 1;
                        while(left < right && nums[left] == nums[left - 1]) {
                            left += 1;
                        }
                    } else if(temp < 0) {
                        left += 1;
                    } else {
                        right -= 1;
                    }
                }
            }
        }
        return res;
    }
}

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                continue
            if(i == 0 or nums[i] != nums[i-1]):
                left = i + 1
                right = len(nums) - 1
                while left < right:
                    if nums[left] + nums[right] == -nums[i]:
                        res.append([nums[i], nums[left], nums[right]])
                        left += 1
                        right -= 1
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1
                    elif nums[left] + nums[right] + nums[i] < 0:
                        left += 1
                    else:
                        right -= 1
        return res

Time complexity: $O(n^2)$.