leetcode每日一题（2020-06-12）：15. 三数之和

题目描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。



今日学习：
1.二维数组去重
2.set和map要想像数组一样使用，需要Array.from()


题解1：
（超时了，多余的计算太多，虽然不是三重循环，但是还不如三重循环）
首先想到三重循环，但是时间肯定会超时，然后想到两数之和加的思想：target-i=j，遍历i找j→改为target = x + y + z,遍历x，target - x = y + z，利用两数相加找出y和z

超时
var threeSum = function(nums) {
    if(nums.length < 3) {return []}
    const res = []
    for(let i = 0; i < nums.length; i++) {
        let target = 0 - nums[i]
        let pre = twoSum(nums, target, i)
        if(pre.length) {
            for(let j = 0; j < pre.length; j++) {
                if(i != pre[j][0] && i!= pre[j][1]) {
                    res.push([nums[i], nums[pre[j][0]], nums[pre[j][1]]])
                }
            }
        }
    }
    for(let i = 0; i < res.length; i++) {
        res[i].sort((a,b)=>a-b)
    }
    let result = single(res)
    return result
};
//两数之和
var twoSum = function(nums, target, n) {
    let arr = []
    for(let i = 0; i < nums.length; i++) {
        if(i != n){
            var diff = target - nums[i];
            if(nums.indexOf(diff) != -1 && nums.indexOf(diff) != i){
                arr.push([i, nums.indexOf(diff)])
            }
        }
    }
    if(arr.length > 0){ return single(arr) }
    return []
};
//二维数组去重
var single = function(nums) {
    let hash = {};  
    let result = []; 
    for(var i = 0, len = nums.length; i < len; i++){  
        if(!hash[nums[i]]){  
            result.push(nums[i]);  
            hash[nums[i]] = true;  
        }  
    }
    return result
}

题解2：
排序+双指针，保证不重复

var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;
    nums.sort((a, b) => a - b); // 排序
    for (let i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L<R && nums[L] == nums[L+1]) L++; // 去重
                while (L<R && nums[R] == nums[R-1]) R--; // 去重
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }        
    return ans;
};