15. 三数之和

Question:

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

注意：答案中不可以包含重复的三元组。

Example:

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

很容易想到，对所有组合进行求解，3层循环：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
   /** 
    * 1. 不能重复
    * 2. x+y+z=0
    * 3. 边界条件处理
    */
    let i, j, k;
    const result = [];
    const hashMap = {};
    const len = nums.length;
    for( i=0; i< len-2; i++ ){
        for( j=i+1; j< len-1; j++) {
            for(k=j+1; k<len; k++) {
                if(nums[i]+nums[j]+nums[k] === 0) {
                    const tempArr = [nums[i], nums[j], nums[k]];
                    const hashKey = tempArr.sort().join('/'); // 去重
                    if(!hashMap[hashKey]) {
                        hashMap[hashKey] = 1;
                        result.push(tempArr);
                    }
                }
            }
        }
    }
    return result;

};

时间复杂度O(n^3)，空间复杂度 O(n), 兴高采烈的提交，然后得到一个报错：

嗯？对其进行优化：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {

   /** 
    * 1. 不能重复
    * 2. x+y+z=0 => x+y = -z , 转换成2数求和的绝对值等于第3数
    */
    let i, j, k;
    const result = [];
    const hashMap = {};
    const resMap = {};
    const len = nums.length;
    // 边界
    if(len < 3){
        return result;
    }
    for( i = 0; i < len - 1; i++ ){
        for( j = i + 1; j < len; j++) {
            console.log(nums[i], nums[j])
            if(hashMap[nums[j]] !== undefined) {
                const resItem = [nums[i], nums[j], hashMap[nums[j]]];
                const resMapKey = resItem.sort().join('');
                if(!resMap[resMapKey]) {
                    result.push(resItem);
                    resMap[resMapKey] = 1;
                }
                hashMap[nums[j]] = undefined
            } else {
                const third = 0 - nums[i] - nums[j];
                hashMap[third] = nums[j];
                console.log(hashMap)
            }
        }
    }
    return result;

};