DEV Community

smolthing
smolthing

Posted on • Edited on

1

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

Image description

  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

Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)