15. 3Sum

Description：

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

思路：

题目要求找出所有三个和为 0 的元素构成的非重复三元数组。首先对数组进行一个排序，排序后循环先取一个数固定，用双指针分别指向当前元素的下一个和数组尾数，判断三者的和与 0 的大小来移动两个指针，并进行去重。

Kotlin代码实现：

 fun threeSum(nums: IntArray): List<List<Int>> {
    val answer: ArrayList<List<Int>> = ArrayList()
    val length = nums.size
    if (length < 3) return answer
    Arrays.sort(nums)
    for (i in 0 until length) {
        if (nums[i] > 0) break

        if (i > 0 && nums[i] == nums[i - 1]) continue

        var left = i + 1
        var right = length - 1
        while (left < right) {
            val sum = nums[i] + nums[left] + nums[right]
            if (sum == 0) {
                answer.add(listOf(nums[i], nums[left], nums[right]))

                while (left < right && nums[left] == nums[left + 1]) left++
                while (left < right && nums[right] == nums[right - 1]) right--
                left++
                right--
            } else if (sum < 0){
                left++
            } else if (sum > 0){
                right--
            }
        }
    }
    return answer
}

参考： https://leetcode.com/problems/3sum/solution/