问题
1.两数相加
方式1:
//如果使用暴力穷举,复杂度是n^2
//使用哈希优化后是n
function twoSum(nums,target){
let map = new Map()
nums.foreach((n,i)=>{
map.add(n,i)
})
for(let i=0;i<nums.length;i++){
const other = target-nums[i];
//不能是自身
if(map.get(other)&&other!==nums[i]){
return[i,map.get(other)]
}
}
return [-1,-1];
}
方式2:
function twoSum(nums=[]){
this.map = new Set()
this.nums = nums
}
twoSum.prototype.add = (n)=>{
for(let v of this.nums){
map.add(v+n)
}
nums.push(n)
}
twoSum.protoType.find = (target)=>{
return this.map.has(target)
}
当数组的值是有顺序时,使用双指针解