15. 3Sum

by Aaron • 10/22/2022, 8:51:42 AM

Description

Medium

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.

TypeScript

function threeSum(nums: number[]): number[][] {
  let ans: Array<Array<number>> = [];
  nums = nums.sort((a, b) => a - b);
  for (let idx = 0; idx < nums.length; idx++) {
    const num = nums[idx];
    if (idx > 0 && num === nums[idx - 1]) continue;
    let left: number = idx + 1;
    let right: number = nums.length - 1;

    while (left < right) {
      if (left > idx + 1 && nums[left] === nums[left - 1]) {
        left++;
        continue;
      }
      if (right < nums.length - 1 && nums[right] === nums[right + 1]) {
        right--;
        continue;
      }

      const sum: number = num + nums[left] + nums[right];

      if (sum === 0) {
        ans.push([num, nums[left], nums[right]]);
        left++;
      } else if (sum > 0) {
        right--;
      } else {
        left++;
      }
    }
  }
  return ans;
}

Python3

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        for idx, n1 in enumerate(nums):
            if (idx > 0 and n1 == nums[idx-1]): continue

            left, right = idx+1, len(nums)-1
            while (left < right):
                if (left > idx+1 and nums[left] == nums[left-1]):
                    left+=1
                    continue

                if (right < len(nums)-1 and nums[right] == nums[right+1]):
                    right-=1
                    continue

                _sum = nums[left] + nums[right] + n1
                if (_sum == 0):
                    ans.append([n1, nums[left], nums[right]])
                    left += 1
                elif (_sum > 0): right-=1
                elif (_sum < 0): left+=1
        return ans

Golang

func threeSum(nums []int) [][]int {
    ans := [][]int{}

    sort.Ints(nums[:])
    for idx, num := range nums {
        if idx > 0 && num == nums[idx-1] {
            continue
        }

        left := idx +1
        right := len(nums) -1

        for left < right {
            if left > idx+1 && nums[left] == nums[left-1] {
                left++
                continue
            }
            if right < len(nums)-1 && nums[right] == nums[right+1] {
                right--
                continue
            }

            sum := num + nums[left] + nums[right]

            if (sum == 0) {
                triplets := []int{num, nums[left], nums[right]}
                ans = append(ans, triplets)
                left++
            } else if (sum > 0) {
                right--
            } else {
                left++
            }
        }
    }
    return ans
}