1、two sum
给出一个数组，和一个整数，返回数组中两个数的和等于整数的数的位置。假设唯一解
例如：[2,7,11,15],target=9
return [0,1]
思路：
- 两遍for循环遍历，但复杂度过高
- 先设置一个对象，key为nums[i],value为i，然后遍历一遍即可，3sum就先设置对象，然后遍历2遍。
var twoSum = function(nums, target) {
var result=[];
var arr={};
for(var i=0;i<nums.length;i++){
arr[nums[i]]=i;
}
for(var i=0;i<nums.length;i++){
var n=target-nums[i];
if((n in arr) && (arr[n]!=i )){
result.push(i,arr[n]);
return result;
}
}
return result;
}
2、3 sum
给出一个数组，和一个整数，返回数组中三个数的和等于0的数。假设好多组。
eg. S=[-1,0,1,2,-1,-4]
return [-1,0,1],[-1,-1,2]
思路：由于返回的是数，可以先进行排序，然后设置两个指针，头l尾r，做一遍for循环，每次判断两个指针相加的大小和0-nums[i]的比较，若大于这个值就r指针减1，小于这个值就l指针加1;若相等。则l++，r--接着查找。查找的过程中要注意去重，如果nums[l] === nums[l+1] 或者nums[r] === nums[r - 1] 则进行l++或者r--的操作。
var threeSum = function(nums) {
nums.sort((a, b) => a - b);
let res = [];
for (let i = 0; i< nums.length - 2; i++) {
let l = i + 1;
let r = nums.length - 1;
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
while(l < r) {
if (nums[l] + nums[r] === 0 - nums[i]) {
res.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(nums[l] + nums[r] < 0 - nums[i]) {
l++;
} else if (nums[l] + nums[r] > 0 - nums[i]) {
r--;
}
}
}
return res;
};
3、4sum
题目：找到四个数的和等于target
思路：3sum的时候是遍历一遍，即确定c，然后用指针的形式找到a和b，a+b=target-c。4sum的时候即可以用a+b=target-（c+d）。一个长度为n的数组有n（n-1）/2个组合的两个数，因此可以分为以下步骤，
1、构造任意两个元素相加得到的集合。
2、对这个集合进行排序。
3、查找即合里符合（a+b）+（c+d）=sum的值。
要设置合理的数据结构定位两个index，但有一个问题，采用对象方式加入的话就会有重复的问题，不知道咋整？？？
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
nums.sort((a, b) => a - b); // 升序排列
var res = [];
for(var i = 0; i< nums.length - 3; i++) {
if(i > 0 && nums[i] === nums[i - 1]) continue;
for(var j = i + 1; j < nums.length - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
var left = j + 1;
var right = nums.length - 1;
while(left < right) {
if (nums[i] + nums[j] + nums[left] + nums[right] === target) {
res.push([nums[i], nums[j], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (nums[i] + nums[j] + nums[left] + nums[right] < target) {
left ++;
} else {
right--;
}
}
}
}
return res;
};
5、3sum closet
题目：找到三个数的和最接近目标值的三个数
思路：同3sum一样，不同的只是判断每次三个数的和的绝对值和上次的三个数的和的绝对值谁更接近target，若更接近则替换掉。
var threeSumClosest = function(nums, target) {
var sum=0;
nums.sort(function(a,b){
return a-b;
});
while(nums.length<=3){
for(var i=0;i<nums.length;i++){
sum=sum+nums[i];
}
return sum;
}
var res=nums[0]+nums[1]+nums[2];
for(var i=0;i<nums.length;i++){
var l=i+1;
var r=nums.length-1;
while(l<r){
n=nums[l]+nums[r]+nums[i];
if(Math.abs(target-n)<Math.abs(target-res)){
res=n;
if(res==target){
return res;
}
}
(n>target)?r--:l++;
}
}
return res;
};
6、two sum II
给出的数组已排好序，求相加等于target的位置，从1开始
var twoSum = function(numbers, target) {
var l=0;
var r=numbers.length-1;
while(l<r){
if(numbers[l]+numbers[r]==target){
return [l+1,r+1]
}else if(numbers[l]+numbers[r]<target){
l++
}else if(numbers[l]+numbers[r]>target){
r--
}
}
};
