力扣每日一题-两数之和+三数之和

2.两数之和

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

题目2：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

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

解答：

1.自己最初的笨方法如下：（我发现真是就会写笨方法！！！我会努力的，每天努力一点点！！！）

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
 for (i=0; i<nums.length-1; i++){       //i<nums.length也可以，后面的j已经给了他约束                                         //条件了，j=i+1先越一下界也没关系！！！
     for(j=i+1; j<=nums.length-1; j++){
        if(nums[j] +nums[i] == target){
          return [i,j]
        }
     }
 }
 return [];  //注意这里，return要写在方法最下面，刚刚出现了非常低级的错误！！放在了for循环里
};

2.使用map

javascript也有map和set数据类型。

首先，先介绍一下map集合的特点（源自https://blog.csdn.net/SuLYi/article/details/76769010）：map集合特点就是采用了 Key-value键值对映射的方式进行存储，key在Map里面是唯一的但是value可以重复，一个key对应一个value。

key是无序、唯一的

value是无序不唯一的

Map接口有两个集合HashMap和TreeMap及LinkedHashMap

HashMap采用哈希表的存储结构所以里面的数据是无序但是唯一的。(实现唯一的方式就是重写 Hashcode和equals方法)

TreeMap采用的是二叉树的存储方式里面的数据是唯一而且有序的而且一般是按升序的方式排列（要实现comparable接口并且重写compareTo的方法用来实现它的排序）

LinkedHashMap是HashMap的进化版它比HashMap速度更快而且还可以保证唯一性和有序性。（它的实现方式是哈希表和链表的结合）

javascript中map的用法

声明

1	var map = new Map();

设值(key数字 value下标)

1	map.set("key","value");

取值

1	map.get("key");

判断key是否存在

1	map.has("key");

删除key

1	map.delete("key");

那么代码的思路就是，先定义一个map集合，然后遍历数组，得到target与当前数值的差，然后看map集合里是否有这个对应的差值，若有，则返回。若没有，则写入map中（也就是说遍历数组中的第一个数时，肯定是写入，因为map中还是空的……）。然后循环。

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

3.先遍历数组，然后看目标值与当前遍历到的数值的差值是否存在于数组之中，若存在则继续判断这个差值是否为本身遍历到的这个数值（即一个数是否用了两遍），若不是，则返回当前数值的索引值和差值的索引值。

var twoSum = function (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums.indexOf(target - nums[i]) != -1) {
            let lastIndex = nums.findIndex((s) => s === (target - nums[i]));
            if (i != lastIndex) {
                return [i, lastIndex]
            }
        }
    }
};

加油加油加油！！！

每天进步一点点啊！！！

希望明年可以找到一个好的offer!!!

15. 三数之和

题目

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

题解

1.给数组排序

2.遍历数组，从0遍历到length-2(为什么? )

3.如果当前的数字等于前一个数字，则跳过这个数（为什么? )

4.如果数字不同，则设置start = i+1,end=length-1，查看i, start和end三个数的和比零大还是小，如果比0小,start++，如果比0大,end–,如果等于0，把这三个数加入到结果里

5.返回结果

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const result = [];
    nums.sort((a,b)=>{
        return a-b;
    })
    for(i=0;i<nums.length-2;i++){  
        if(i===0||nums[i-1] !== nums[i]){
            let start = i+1;
            let end = nums.length-1;
            while(start<end){
                if(nums[i]+nums[start]+nums[end] < 0){
                    start++;
                }else if(nums[i]+nums[start]+nums[end] > 0){
                    end--;
                }else{
                    result.push([nums[i],nums[start],nums[end]]) 
                    start++;
                    end--; 
                    while(start<end && nums[start] === nums[start-1]){
                        start++;
                    }
                    while(start<end && nums[end] === nums[end+1]){
                        end--;
                    }
                }
            } 
       
        }
    }
   return result;
};

第二种（还没仔细看）其实和第一道题解类似。

var threeSum = function(nums) {
	if(nums.length<3) return [];  // 数组小于三个元素，不符合题意
    
    let len = nums.length;
    nums.sort((a, b) => a - b);  // 按数字大小排序便于剪枝
			
	let result = [];
    let left;  // 左指针
    let right;  // 右指针
    let count;
	for(let i=0;i<len-2;i++) {
        if(nums[i]==nums[i-1]) continue;  // 去重剪枝
        if(nums[i]+nums[i+1]+nums[i+2]>0) break;  // 若连续三个最小的数之和都大于0，后面不可能有解
        if(nums[i]+nums[len-2]+nums[len-1]<0) continue; // 若nums[i]加最大两个数都小于0，则nums[i]无解
        left = i+1;
        right = len-1;
        while(left<right){
            count = nums[i]+nums[left]+nums[right];
            if(count<0) left++;  // 如果和小于0，左指针右移
            else if (count>0) right--;  // 如果和大于0，右指针左移
            else {
                result.push([nums[i], nums[left], nums[right]]);

                // 去重剪枝
                while(left<right && nums[left]==nums[left+1]) left++;
                while(left<right && nums[right]==nums[right-1]) right--;

                left++;
                right--;  // 求出正确解之后应该同时移动左、右指针
                // 这是因为a+b+c=0，若a,b不变，则c也不会变，但题目要求不能有重复解，所以左右指针都要移动
            }
        }
	}
	return result;
};