给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。提示：
题目信息：nums[i] + nums[j] + nums[k] == 0，不重复且顺序并不重要
暴力循环 3 层，复杂度 O(n3)，需要降复杂度，哈希降一层，复杂度 O(n2)
发现需要去重，需要单独去重，避免在循环内提高复杂度
发现会内存溢出，不能单独去重，在循环内去重并使用 hash 降低复杂度
哈希法去重性能太差，三指针法滑动效率更高，i 遍历，j,k 在后面的左和右边，j 向右移动，大于 0 则 k 向左移动，直到 jk 相遇
// 暴力循环3层，复杂度O(n3)，需要降复杂度
// 哈希降一层，复杂度O(n2)
function threeSum(nums: number[]): number[][] {
// nums[j]+nums[k]===-nums[i]
// 哈希存nums[i]
const hash = {}
let res = []
for (let i = 0; i < nums.length; i++) {
hash[-nums[i]] = i
}
for (let j = 0; j < nums.length; j++) {
for (let k = 0; k < nums.length; k++) {
// 条件
const iIndex = hash[nums[j] + nums[k]]
const isDiffIndex = iIndex !== j && iIndex !== k && j !== k
if (hash[nums[j] + nums[k]] !== undefined && isDiffIndex) {
const arr = [-(nums[j] + nums[k]), nums[j], nums[k]]
console.log(arr)
// 去重
if (!res.some((i) => isSameArray(i, arr))) {
res.push(arr)
}
}
}
}
return res
}
function isSameArray(arr1: number[], arr2: number[]) {
const hash = {}
for (let i = 0; i < arr1.length; i++) {
hash[arr1[i]] = hash[arr1[i]] ? hash[arr1[i]] + 1 : 1
}
for (let j = 0; j < arr2.length; j++) {
const isDiff = !hash[arr2[j]]--
if (isDiff) {
return false
}
}
return true
}// 暴力循环3层，复杂度O(n3)，需要降复杂度
// 哈希降一层，复杂度O(n2)
// 发现需要去重，需要单独去重
function threeSum(nums: number[]): number[][] {
// nums[j]+nums[k]===-nums[i]
// 哈希存nums[i]
const hash = new Map()
let res = []
for (let i = 0; i < nums.length; i++) {
hash.set(-nums[i], i)
}
for (let j = 0; j < nums.length; j++) {
for (let k = 0; k < nums.length; k++) {
// 条件
const iIndex = hash.get(nums[j] + nums[k])
const isDiffIndex = iIndex !== j && iIndex !== k && j !== k
const isRes = iIndex !== undefined
if (isRes && isDiffIndex) {
const arr = [-(nums[j] + nums[k]), nums[j], nums[k]]
res.push(arr)
}
}
}
// 去重
const uniqueRes = unique(
res.map((i) => i.sort((a, b) => a - b).toString()),
).map(toNumberArray)
return uniqueRes
}
function unique(arr: any[]) {
return Array.from(new Set(arr))
}
function toNumberArray(str: string) {
return str.split(',').map((i) => parseInt(i))
}// 暴力循环3层，复杂度O(n3)，需要降复杂度
// 哈希降一层，复杂度O(n2)
// 发现需要去重，需要单独去重
// 发现会内存溢出，不能单独去重
function threeSum(nums: number[]): number[][] {
// nums[j]+nums[k]===-nums[i]
// 哈希存nums[i]
const iHash = new Map()
let stringHash = new Map()
const uniqueRes = []
for (let i = 0; i < nums.length; i++) {
iHash.set(-nums[i], i)
}
for (let j = 0; j < nums.length; j++) {
for (let k = 0; k < nums.length; k++) {
// 条件
const iIndex = iHash.get(nums[j] + nums[k])
const isDiffIndex = iIndex !== j && iIndex !== k && j !== k
const isRes = iIndex !== undefined
if (isRes && isDiffIndex) {
const arr = [-(nums[j] + nums[k]), nums[j], nums[k]]
const str = arr.sort((a, b) => a - b).toString()
// 字符串化去重
if (!stringHash.has(str)) {
stringHash.set(str, true)
// 数组化返回结果
uniqueRes.push(toNumberArray(str))
}
}
}
}
return uniqueRes
}
function toNumberArray(str: string) {
return str.split(',').map((i) => parseInt(i))
}// 暴力循环3层，复杂度O(n3)，需要降复杂度
// 哈希降一层，复杂度O(n2)
// 发现需要去重，需要单独去重
// 发现会内存溢出，不能单独去重
// 哈希法去重性能太差，三指针法滑动效率更高
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b)
const res = []
const hash = new Map()
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1, k = nums.length - 1; j < k; ) {
const sum = nums[i] + nums[j] + nums[k]
if (sum < 0) {
j++
} else if (sum > 0) {
k--
} else {
const arr = [nums[i], nums[j], nums[k]]
const key = arr.toString()
if (!hash.has(key)) {
res.push(arr)
hash.set(key, true)
}
j++
k = nums.length - 1
}
}
}
return res
}