LeetCode T15 - 3Sum

LeetCode T 15: 3Sum是一个比较普通的问题，考验一定的思维和编程能力。

描述：给定一个长为$n$的数组nums，请问数组中是否包含三个元素a, b, c, 使得 a + b + c = 0? 找到数组中所有这类元素的三元组。

注意：
解决方案中不得包含重复的三元组。

例子：

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

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

从题目我们可以知道，需要找到所有不重复的$(a, b, c)$，使得$a + b + c = 0$。这里有一个关键点：不重复。

为达到这个目标，首先我们需要对原数组进行排序，以进行序列的比较筛除重复的元素。如：[0, 0, 0, 0]，如果不进行筛除，将会得到[[0, 0, 0], [0, 0, 0]]，这是不符合规范的。
同时，我们需要进行搜索，需要一定的时间优化。如果用暴力，将是$O(n^3)$的时间复杂度，这将是非常令人不满的。因为LeetCode会报TLE。
于是，设计了一个思路：指针i, j, k分别指向三个元素，i从0开始迭代到len(nums)-2，j从i+1开始迭代到len(nums)-1，k采用二分查找。

最后代码是这样(Golang)：

func threeSum(nums []int) [][]int {
    // 排序
    sort.Ints(nums)
    lens := len(nums)
    var matrix [][]int
    // 长度不够，返回空
    if len(nums)<=2 {
        return matrix
    }
    for i := 0; i < lens-2; i++ {
        // 第一个元素就>0, 意味着所有元素>0
        if  nums[0] > 0 {
            break
        }
        for j := i + 1; j < lens-1; j++ {
            l := j + 1
            r := lens - 1
            // 二分查找
            for l < r {
                if l == r-1 {
                    if nums[i]+nums[j]+nums[l] == 0 {
                        matrix = append(matrix, []int{nums[i], nums[j], nums[l]})
                    } else if nums[i]+nums[j]+nums[r] == 0 {
                        matrix = append(matrix, []int{nums[i], nums[j], nums[r]})
                    }
                    break
                }
                mid := (l + r) / 2
                if nums[i]+nums[j] < -nums[mid] {
                    l = mid
                } else if nums[i]+nums[j] > -nums[mid] {
                    r = mid
                } else {
                    matrix = append(matrix, []int{nums[i], nums[j], nums[mid]})
                    for j < lens-1 && nums[j] == nums[j+1] {
                        j++
                    }
                    break
                }
            }
            // 只有1个元素的特殊情况
            if l == r {
                if nums[i]+nums[j]+nums[l] == 0 {
                    matrix = append(matrix, []int{nums[i], nums[j], nums[r]})
                }
            }
            // 迭代完成，去除重复元素
            for j < lens-1 && nums[j] == nums[j+1] {
                j++
            }

        }
        // i迭代完成，去除重复元素
        for i < lens-2 && nums[i] == nums[i+1] {
            i++
        }
    }
    return matrix
}

这个答案依然不是最好的，时间已经是1024ms，超过了一般规定的1000ms。其实，3Sum问题本质上是2Sum问题。因为a = -(b+c)，所以a从0迭代到len(nums)-2，只要保证j，k构成的2Sum和a加起来是0就正确。这就是最优的解决方案。