3Sum

The 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.

The idea

1. Array must be sorted.
2. Iterate through the list + Left and right pointer.
3. Result must be a set because they may be duplicate values.
4. Order of the tuple (current value, left pointer, right pointer) inserted into result matters.

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = set()
        nums.sort()
        for i in range(len(nums) - 2):
            currentValue = nums[i]

            left = i + 1
            right = len(nums) - 1

            while left < right:
                totalSum = currentValue + nums[left] + nums[right]
                if totalSum > 0:
                    right -= 1 // if there is no negative value, left += 1 will only increase totalSum
                elif totalSum < 0:
                    left += 1
                else:
                    result.add((currentValue, nums[left], nums[right]))
                    left += 1
                    right -= 1

        return result

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();

        for (int i = 0; i<nums.length - 2; i++) {
            int currentValue = nums[i];

            int start = i + 1;
            int end = nums.length - 1;

            while (start < end) {
                int total = currentValue + nums[start] + nums[end];
                if (total < 0) {
                    start += 1;
                } else if (total > 0) {
                    end -= 1;
                } else {
                  set.add(Arrays.asList(currentValue, nums[start], nums[end]));
                    start += 1;
                    end -= 1;
                }
            }
        }

        return new ArrayList<>(set);
    }
}