# 数组，哈希，双指针

# 1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var mymap = new Map();
    for(var i=0; i< nums.length; i++) {
        mymap.set(nums[i], i);
    }
    for(var i=0; i<nums.length; i++) {
        var rest = target - nums[i];
        if (mymap.get(rest) && mymap.get(rest) != i) {
            return [i, mymap.get(rest)];
        }
    }
}

感受: 两数之和，一开始我想的比较简单，通过暴力法来做，就是遍历，然后相加比较，其实其中多了很多重复的步骤。

在后来想到了可以通过hash的方法，一开始将所有的都放入，再一个个找是否剩下的里面，有对应点target-arr【i】的hash.

js中实现hashmap通过new Map(); 再set(),get()的方法进行读取。

# 167. 两数之和 II - 输入有序数组

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    var len = numbers.length;
    var l = 0;
    var r = len -1;
    while(l<r) {
        if(numbers[l] + numbers[r] == target) {
            return [l+1, r+1];
        } 
        if(numbers[l] + numbers[r] < target) {
            l ++;
        }
        if(numbers[l] + numbers[r] > target) {
            r --;
        }
    }
};

感受:两个数之和的问题大部分都可以通过双指针来解决

# 15. 三数之和

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

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

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

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

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    var arr = [];
    var len = nums.length;
    if (nums == null || len < 3) return arr;
    nums.sort((a,b) => a-b);
    for(var i =0 ;i<len; i++) {
        if(nums[i] > 0) break;
        if(i> 0 && nums[i] == nums[i-1]) continue;
        var l = i+1;
        var r = len-1;
        while(l<r) {
            var sum = nums[i] + nums[l] + nums[r];
            if(sum == 0) {
                arr.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 -- ;
            }
            if (sum < 0) l++;
            if (sum > 0) r--;
        }
    }
    return arr;
};

感受:三数之和，有点类似两数之和，一开始会这么想。

现在我发现，如果有多个数字进行比较，有时候我们会选择先固定一个数字，或者2个，或者更多，再将其他点剩下点进行比较。

多个数字比较，可能可以考虑到多个指针，一般为双指针法,同时最好一开始排序一下，这样的话，容易进行后续比较，按顺序来，可能会将一些边界点问题很容易处理掉，比如说比第一个都小，就直接不满足，或者比最大的都大也不满足。在排序以后，容易处理掉，去重问题，只需要比较相邻点是否相同，可能选择跳过，index索引可以直接跳过。

# 16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

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

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
        nums.sort((a,b) => a-b);
        var ans = nums[0] + nums[1] + nums[2];
        for(var i=0;i<nums.length;i++) {
            var start = i+1, end = nums.length - 1;
            while(start < end) {
                var sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
};

感受:类似611 有效三角形个数

其实通过双指针法，跟那个几乎一样

找到最大固定在右边，然后从大往小遍历。

# 259. 较小的三数之和

给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。

示例：

输入: nums = [-2,0,1,3], target = 2 输出: 2 解释: 因为一共有两个三元组满足累加和小于 2: [-2,0,1] [-2,0,3]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumSmaller = function(nums, target) {
    nums.sort((a,b) => a-b);
    var result = 0;
    for(var i = 0 ;i <nums.length ;i++) {
        var l = i+1;
        var r = nums.length -1;
        while(l<r) {
            sum = nums[i] + nums[l] + nums[r];
            if(sum >= target) {
                r --;
            } else {
                result ++;
                l ++;
            }
        }
    }
    return result;
};

# 611. 有效三角形的个数

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 注意:

数组长度不超过1000。数组里整数的范围为 [0, 1000]。

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
    nums.sort((a,b) => a-b);
    var len = nums.length;
    var count = 0;
    for(var i= len -1; i>=2; i--){
        var l = 0;
        var r = i - 1;
        while(l<r) {
            if(nums[l] + nums[r] > nums[i]) {
                count += r - l;
                r --;
            } else {
                l++;
            }
        }
    }
    return count;
};

感受:三个数字有效问题，其实是三数之和类似，固定一个值，最大值，再双指针比较，

需要注意，不用去重，同时还是要先排序，比较点时候点index如何设置很关键，设置最大值固定，那个就是index，设置为nums的长度-1；剩下的l,r其实是0,index-1;

如果找到大的，那么他左边的就都是，同时右指针向左移动。如果小的话，左指针继续右移。

# 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) {
    nums.sort((a,b) => a-b);
    var len = nums.length;
    var result = [];
    for(var i=0;i<len-3;i++) {
        if(i>=1 && nums[i] == nums[i-1]) continue;
        n1 = i;
        for(j=i+1;j<len-2;j++) {
            if(j>i+1 && nums[j] == nums[j-1]) continue;
            n2 = j;
            var l = n2 + 1;
            var r = len -1;
            while(l<r) {
                if(nums[n1] + nums[n2] + nums[l] + nums[r] == target) {
                    result.push([nums[n1] , nums[n2] , nums[l] , nums[r]]);
                    l++;
                    while(nums[l] == nums[l-1]) l++;
                    while(nums[r] == nums[r-1]) r--;
                } else if(nums[n1] + nums[n2] + nums[l] + nums[r] < target) {
                    l++;
                } else if(nums[n1] + nums[n2] + nums[l] + nums[r] > target) {
                    r--;
                }
            }
        }
    }
    return result;
};

感受:四数之和问题，我们觉得我点问题还是在去重没有搞明白前面固定数字点去重通过跟前一个比较，再continue跳出循环然后后面点是比较l,r和前面是否相同，自增或者自减。

# 454. 四数相加 II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

例如:

输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2]

输出: 2

解释: 两个元组如下:

(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @param {number[]} D
 * @return {number}
 */
var fourSumCount = function(A, B, C, D) {
    var result = 0;
    var map = new Map();
    for(var i=0;i<C.length;i++) {
        for(var j=0;j<D.length;j++) {
            var sum = C[i] + D[j];
            if(map.get(sum)) {
                var num = Number(map.get(sum));
                map.set(sum, ++num);
            } else {
                map.set(sum, 1);
            }
        }
    }

    for(var i=0;i<A.length;i++) {
        for(var j=0;j<B.length;j++) {
            var rest = - (A[i] + B[j]);
            if(map.get(rest)) {
                result += map.get(rest);
            }
        }
    }
    return result;
};

感受:同样四数相加点问题，用指针可能不太行，可以通过一部分确定，然后hash来做。

← 算法-leetcode积累