SOURCE

// 三数之和 返回值不得有重复
const arr = [-1, -1, 0, 1, 2, -4, -1, -1, 0, 1, -1]

// 暴力求解
// const fn = (arr) => {
//     let res = []
//     let map = {}
//     for(let i = 0; i < arr.length; i++){
//         for(let j = i + 1; j < arr.length; j++){
//             for(let k = j + 1; k < arr.length; k++){
//                 let isa = `${arr[i]}${arr[j]}${arr[k]}`
//                 if(map[isa]){
//                     break
//                 }else{
//                     map[isa] = true
//                 }
//                 if(arr[i] + arr[j] + arr[k] === 0){
//                     res.push([arr[i], arr[j], arr[k]])
//                 }
//             }
//         }
//     }
//     return res
// }

// 排序加双指针
const fn = (arr) => {
    let res = []
    let map = {}
    arr.sort((a, b) => a - b)
    for (let i = 0; i < arr.length; i++) {
        // 第二个数指针
        let j = i + 1
        // 第三个数指针
        let k = arr.length - 1
        // 第一个数
        let first = arr[i]
        if (first > 0) break
        // 去重
        // if (i > 0 && arr[i] === arr[i - 1]) continue
        while (j < k) {
            let second = arr[j]
            let third = arr[k]
            if (first + second + third === 0) {
                let key = `${first}${second}${third}`
                if(map[key]){
                    break
                }
                map[key] = true
                res.push([first, second, third])
                // 去重
                // while (second < third && arr[j] === arr[j + 1]) j++
                // while (second < third && arr[k] === arr[k - 1]) k--
                k--
                j++
            } else if (first + second + third > 0) {
                k--
            } else {
                j++
            }
        }

    }
    return res
}
console.log(fn(arr))