很久之前就想练算法，看过书也就懂个大概，学而不练是为无用，今天开始每天的力扣打卡！（一周争取3-4题吧...视情况而定）
第一题
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
方案一：因为写了很久的代码都没怎么用到算法（或是用到了没有注意到），所以第一反应就是暴力法——两层嵌套循环取得答案，时间复杂度为O(N^2)
```
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let numA = nums
let numB = nums
for (let index in numA) {
for (let index1 in numB) {
if ( numB[index1] + numA[index] == target) {
if (numB[index1] <= numA[index] && index != index1) {
return [index1,index]
}
}
}
}
};
```
但因为我多虑了，以为数组中重复元素是无效的（例如nums = [1,2,3,3],target = 6,[3,3]的组合），导致了第一次的错误。本来是 < ，修改为numB[index1] <= numA[index]
第二次错误则是因为nums = [3,2,4], target = 6, 暴力法两次循环，3 + 3 = 6，2 + 4 = 6,因此在原基础上增加条件&& index != index1，即下标不相等。
但暴力法固然可行，但结果：
结果
次数
太难看了。
方案二：
算法还是小白，翻阅了一些其他回答，有利用js的数组即HashMap的特性，将复杂度降到O(n)
```
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
// 参考其他解决方案后
var temp = [];
for(let i in nums){
var dif = target - nums[i];
if(temp[dif] != undefined){
return [temp[dif],i];
}
temp[nums[i]] = i;
}
};
```
肉眼可见的提高...HashMap真是个好东西，回头还得继续啃《Thinking in Java》唉。具体的更佳算法明天继续打卡加油！
网友评论