two sum

入门题

001 两数之和给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案

链接：https://leetcode-cn.com/problems/two-sum

暴力循环法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(var i = 0 ; i < nums.length ; i++){
        for(var j = i + 1 ; j < nums.length ; j++){
            if(nums[j] === target-nums[i])
                return [i,j];
        }      
    }
    return [-1,-1]
};

哈希表法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var map = new Map();
    //存入哈希表
    for(var i = 0; i <nums.length ; i++){
        map.set(nums[i],i)
    }
    for(var i = 0 ; i <  nums.length ; i++){
        const other = target - nums[i];
        //下标要不同
        if(map.has(other) && map.get(other) !== i ){
            return [i,map.get(other)];
        }
    }
    return [-1,-1];
};

优化一下，查询哈希表是否存在 target - x，否则将 x 插入到哈希表中，即可保证不会让 x 和自己匹配

var twoSum = function(nums, target) {
    var map = new Map();
    for(var i = 0 ; i <  nums.length ; i++){
        if(map.has(target - nums[i])){
            return [map.get(target - nums[i]), i];
        }else{
            map.set(nums[i], i);
        }
    }
    return [-1,-1];
};

两数之和II

给定一个已按照升序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 1 开始计数，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

双指针法

var twoSum = function (nums, target) {
    var l = 0;
    var r = nums.length - 1;
    while (l < r) {
        var sum = nums[l] + nums[r];
        if (sum === target) {
            //下标从1开始计数
            return [l + 1, r + 1];
        } else if (sum < target) {
            l++;
        } else if (sum > target) {
            r--;
        }
    }
    return [-1, -1];
};

引申

假如001题要求返回值而不是下标，可以使用先排序后使用双指针法求解，

var twoSum = function (nums, target) {
//排序，注意js排序是按编码，数字排序必需传函数
nums.sort(function (a, b) {
  return a - b;
});
var l = 0;
var r = nums.length - 1;
while (l < r) {
  var sum = nums[l] + nums[r];
  if (sum === target) {
    //返回值
    return [nums[l], nums[r]];
  } else if (sum < target) {
    l++;
  } else if (sum > target) {
    r--;
  }
}
return [-1, -1];
};

如果数组里满足和的值不唯一，应该怎么做？

var twoSum = function (nums, target) {
  var res = [];
  nums.sort(function (a, b) {
    return a - b;
  });
  var l = 0;
  var r = nums.length - 1;
  while (l < r) {
    var sum = nums[l] + nums[r];
    if (sum === target) {
      res.push([nums[l], nums[r]]);
      l++;
      r--;
    } else if (sum < target) {
      l++;
    } else if (sum > target) {
      r--;
    }
  }
  return res;
};

但是这样，会出现重复：

console.log(twoSum([1,3,1,2,2,3], 4));
//[ [ 1, 3 ], [ 1, 3 ], [ 2, 2 ] ]

如何去重？
数组里重复的直接跳过下标

var twoSum = function (nums, target) {
  var res = [];
  nums.sort(function (a, b) {
    return a - b;
  });
  var l = 0;
  var r = nums.length - 1;
  while (l < r) {
    var sum = nums[l] + nums[r];
    var left = nums[l],
      right = nums[r];
    if (sum === target) {
      res.push([nums[l], nums[r]]);
      while (l < r && nums[l] == left) l++;
      while (l < r && nums[r] == right) r--;
    } else if (sum < target) {
      while (l < r && nums[l] == left) l++;
    } else if (sum > target) {
      while (l < r && nums[r] == right) r--;
    }
  }
  return res;
};

如何优化上述代码？
暂无

three sum

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/3sum

穷举第1个数字，然后调用2Sum函数计算剩下2个数，最后组合出和为target的3元组。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
//通用二元sum函数
var twoSum = function (nums, start, target) {
    var res = [];
    var l = start;
    var r = nums.length - 1;
    while (l < r) {
        var sum = nums[l] + nums[r];
        var left = nums[l],
            right = nums[r];
        if (sum === target) {
            res.push([nums[l], nums[r]]);
            while (l < r && nums[l] == left) l++;
            while (l < r && nums[r] == right) r--;
        } else if (sum < target) {
            while (l < r && nums[l] == left) l++;
        } else if (sum > target) {
            while (l < r && nums[r] == right) r--;
        }
    }
    return res;
};
var threeSum = function (nums) {
    var res = [];
    nums.sort(function (a, b) {
        return a - b;
    });
    for (var i = 0; i < nums.length; i++) {
          //调用twoSum函数
        var res2 = twoSum(nums, i + 1, 0 - nums[i]);
        res2.forEach(r => {
            r.unshift(nums[i]);//头部插入
            res.push(r);
        })
       //用来保证第一个数字不重复
        while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
    }
    return res;
};

如果是4 sum，那么可以再写一层，那么可以抽离出来，写出一个N sum 求解的方法：

//通用nsum函数
var nSum = function (nums, n, start, target) {
    var res = [];
    if (n < 2 ) return res;
    if (n == 2) {
        var l = start;
        var r = nums.length - 1;
        while (l < r) {
            var sum = nums[l] + nums[r];
            var left = nums[l],
                right = nums[r];
            if (sum === target) {
                res.push([nums[l], nums[r]]);
                while (l < r && nums[l] == left) l++;
                while (l < r && nums[r] == right) r--;
            } else if (sum < target) {
                while (l < r && nums[l] == left) l++;
            } else if (sum > target) {
                while (l < r && nums[r] == right) r--;
            }
        }
    } else {
        for (var i = start; i < nums.length; i++) {
            var res2 = nSum(nums, n - 1, i + 1, target - nums[i]);
            res2.forEach(r => {
                r.unshift(nums[i]);
                res.push(r);
            })
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }
    }
    return res;
};

four sum

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/4sum

 var fourSum = function (nums, target) {
    nums.sort(function (a, b) {
        return a - b;
    });
    return nSum(nums, 4, 0, target)
};

刷个算法

Two Sum & N Sum问题