15. 3Sum

Đề bài

Cho mảng số nguyên nums gồm n phần tử. Hãy tìm tất cả các bộ ba $(a, b, c)$ sao cho:

• $a + b + c = 0$
• Mỗi bộ ba trong kết quả là không trùng lặp (không được có các hoán vị của cùng một bộ ba).

Ví dụ:

Input: nums = [-1, 0, 1, 2, -1, -4]
Output:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Tóm tắt đề

Trả về danh sách tất cả các bộ ba khác nhau có tổng bằng 0.

Lưu ý về “khác nhau”:

• [-1, -1, 2], [-1, 2, -1], [2, -1, -1] được xem là một kết quả (chỉ lấy một lần).

Ý tưởng

Có nhiều cách, trong file này có 2 cách:

• Cách 1 (khuyến nghị): Sort + 2 con trỏ (two pointers) để đạt $O(n^2)$, đồng thời bỏ qua các phần tử trùng để tránh kết quả lặp.
• Cách 2: Đếm tần suất bằng map rồi duyệt trên danh sách các giá trị phân biệt (cũng $O(n^2)$ theo số lượng giá trị khác nhau), tự xử lý các trường hợp dùng 2 hoặc 3 lần cùng một số.

Code

package leetcode

import (
	"sort"
)

// Cách 1: tối ưu - sắp xếp + 2 con trỏ
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	result, start, end, index, addNum, length := make([][]int, 0), 0, 0, 0, 0, len(nums)
	for index = 1; index < length-1; index++ {
		start, end = 0, length-1
		if index > 1 && nums[index] == nums[index-1] {
			start = index - 1
		}
		for start < index && end > index {
			if start > 0 && nums[start] == nums[start-1] {
				start++
				continue
			}
			if end < length-1 && nums[end] == nums[end+1] {
				end--
				continue
			}
			addNum = nums[start] + nums[end] + nums[index]
			if addNum == 0 {
				result = append(result, []int{nums[start], nums[index], nums[end]})
				start++
				end--
			} else if addNum > 0 {
				end--
			} else {
				start++
			}
		}
	}
	return result
}

// Cách 2: dùng map đếm tần suất + duyệt các giá trị phân biệt
func threeSum1(nums []int) [][]int {
	res := [][]int{}
	counter := map[int]int{}
	for _, value := range nums {
		counter[value]++
	}

	uniqNums := []int{}
	for key := range counter {
		uniqNums = append(uniqNums, key)
	}
	sort.Ints(uniqNums)

	for i := 0; i < len(uniqNums); i++ {
		if (uniqNums[i]*3 == 0) && counter[uniqNums[i]] >= 3 {
			res = append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i]})
		}
		for j := i + 1; j < len(uniqNums); j++ {
			if (uniqNums[i]*2+uniqNums[j] == 0) && counter[uniqNums[i]] > 1 {
				res = append(res, []int{uniqNums[i], uniqNums[i], uniqNums[j]})
			}
			if (uniqNums[j]*2+uniqNums[i] == 0) && counter[uniqNums[j]] > 1 {
				res = append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j]})
			}
			c := 0 - uniqNums[i] - uniqNums[j]
			if c > uniqNums[j] && counter[c] > 0 {
				res = append(res, []int{uniqNums[i], uniqNums[j], c})
			}
		}
	}
	return res
}

---