基础理论

排序
low high 指针

练习

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

两数之和 就不能使用双指针法，因为1.两数之和要求返回的是索引下标， 而双指针法一定要排序，一旦排序之后原数组的索引就被改变了。
如果1.两数之和要求返回的是数值的话，就可以使用双指针法了。

  2. 解法一：
  3. var twoSum = function (numbers, target) {
  5.     for (var i = 0; i < numbers.length - 1; i++) {
  6.         for (var j = i + 1; j < numbers.length; j++) {
  7.             if (numbers[i] + numbers[j] === target) return [i, j];
  8.         }
  9.     }
  10. };
  13. 解法二：
  14. var twoSum = function (nums, target) {
  15.       const map = {};
  16.       if (Array.isArray(nums)) {
  17.         for (let i = 0; i < nums.length; i++) {
  18.           if (map[target - nums[i]] != undefined) {
  19.             return [map[target - nums[i]], i];
  20.           } else {
  21.             map[nums[i]] = i;
  22.           }
  23.         }
  24.       }
  25.       return [];
  26. };

15. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
参考：https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.md

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// Two Pointer
var threeSum = function(nums) {
    var len = nums.length;
    var res=[];
    if(len<2 ) return res;

    nums = nums.sort((a,b) => a-b);

    for(var i =0;i<len-2;i++){
        //去重
        if(i>0 && nums[i]==nums[i-1]) continue

        var low = i+1;
        var high = len - 1;
        var sum = 0 - nums[i];

        while(low < high ){
            if(nums[low]+nums[high]==sum){
                res.push([nums[i],nums[low],nums[high]])
                //去重
                while(low<high && nums[low]==nums[low+1]) low++
                while(low<high && nums[high] == nums[high-1]) high--
                low++;
                high--
            } else if(nums[low]+nums[high] < sum){
                low++;
            } else{
                high--;
            }

        }
    }
    return res;  
};

18.四数之和

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

示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
//思路同三数之和
var fourSum = function(nums, target) {
        var len = nums.length;
        var res=[];
        if(len< 4 ) return res;

        nums = nums.sort((a,b) => a-b);

        for(var i=0;i<len-3;i++){
            if(i>0 && nums[i]== nums[i-1]) continue

            for(var j=i+1;j<len-2;j++){
                if(j>i+1 && nums[j]==nums[j-1]) continue

                var low = j+1;
                var high = len-1;
                var sum = target - nums[i] - nums[j];

                while(low<high){
                    if(nums[low]+nums[high] == sum){
                        res.push([nums[i],nums[j],nums[low],nums[high]])
                        while(low<high && nums[low] == nums[low+1]) low++
                        while(low<high && nums[high] == nums[high-1]) high--
                        low++;
                        high--;
                   } else if(nums[low]+nums[high]<sum){
                       low++
                   } else {
                       high--
                   }
                }
            }
        }

    return res
};

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.md