15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

(1) Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            //rst.add(new ArrayList<Integer>());
            return rst;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            int num1 = nums[i];
            if (i > 0 && num1 == nums[i-1]) {
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while (left < right) {
                int sum = num1+nums[left]+nums[right];
                if ( sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(num1);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    rst.add(list);
                    left++;
                    right--;
                    while ( left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                    while ( left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return rst;
    }
}

(2) Python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        nums.sort()
        rst = []
        for i in range(0, len(nums)-2):
            if i == 0 or nums[i] != nums[i-1]:
                left = i+1
                right = len(nums)-1
                while left < right:
                    sum = nums[left]+nums[right]+nums[i]
                    if sum == 0:
                        triple = [nums[i],nums[left],nums[right]]
                        rst.append(triple)
                        left += 1
                        right -= 1
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
                    elif sum < 0:
                        left += 1
                    else:
                        right -= 1
        return rst

(3) Scala

object Solution {
    def threeSum(nums: Array[Int]): List[List[Int]] = {
        var rst: List[List[Int]] = List()
        if (nums == null || nums.length <=2) {
            return rst
        }
        scala.util.Sorting.quickSort(nums)
        for (i <- 0 until nums.length-2) {
            if (i == 0 || nums(i) != nums(i-1)) {
                var left = i+1
                var right = nums.length-1
                while (left < right) {
                    val sum: Int = nums(i)+nums(left)+nums(right)
                    if (sum == 0) {
                        val list: List[Int] = nums(i)::nums(left)::nums(right)::Nil
                        rst = rst :+ list
                        left += 1
                        right -= 1
                        while (left < right && nums(left) == nums(left-1)) {
                            left += 1
                        }
                        while (left < right && nums(right) == nums(right+1)) {
                            right -= 1
                        }
                    } else if (sum < 0) {
                        left += 1
                    } else {
                        right -= 1
                    }
                }
            }
        }
        return rst                
    }
}