1、大数相加
背景：JS如果数太大显示这个数字都不正确。更不要说相加了。大概16位.
它精度不够。所以存储不了。
image.png
所以两个数字相加太大了容易出现问题。所以写一个算法把他们相加。
题目：
const add = (a, b) => {
...
return sum
}
console.log(add("11111111101234567","77777777707654321"))
console.log(add("911111111101234567","77777777707654321"))
//由于JS不能用数字表达这两个数字所以传的字符串
思路：
每一位两两相加，从后往前遍历，考虑进位情况
overflow标记 如果 大于10就true
如果true下一位就加1
false不加
答案：
const add = (a, b) => {
const maxLength = Math.max(a.length, b.length) //判断长度
let overflow = false//进位标记
let sum = '' //结果
for(let i = 1; i <= maxLength; i++){
const ai = a[a.length-i] || '0' //从最后一位开始取没了就是0
const bi = b[b.length-i] || '0'
let ci = parseInt(ai) + parseInt(bi) + (overflow ? 1 : 0)
overflow = ci >= 10
ci = overflow ? ci - 10 : ci
sum = ci + sum
}
//如果循环结束也就是最后一位还是移除那就给他进一位
sum = overflow ? '1' + sum : sum
return sum
}
console.log(add("11111111101234567","77777777707654321"))
console.log(add("911111111101234567","77777777707654321"))
image.png
这样也可以但是估计不让用
2、两数之和
题目：
numbers中哪两个数之和等于target
const numbers = [2,7,11,15]
const target = 9
const twoSum = (numbers, target) => {
// ...
}
console.log(twoSum(numbers, target))
// [0, 1] 或 [1, 0]
// 出题者保证
// 1. numbers 中的数字不会重复
// 2. 有且仅有一个有效答案
答案：
const numbers = [2,7,11,15]
const target = 9
const twoSum = (numbers, target) => {
const map = {} //利用哈希表来找，用空间换时间。
for(let i = 0; i < numbers.length; i++){
const number = numbers[i]
const number2 = target - number
if(number2 in map){
const number2Index = map[number2]
return [i, number2Index]
} else {
map[number] = i
}
}
}
console.log(twoSum(numbers, target))
可以双重循环但复杂度较高n*n,效率低
我们这个方法效率比较高 只遍历一遍，用一个哈希表做辅助。
思路就是在哈希中找 与numbers[i] 相加等于target的数，没有就把numbers[i]放进去当K 把i当value i也就是他的下标。
用哈希表（可以你给我一个数字我能快速找到它在哪，借助了浏览器的代码）相当于偷懒，这招叫做用空间换时间。时间复杂度2n
3、无重复最长子串的长度（滑动窗口）
题目：
const lengthOfLongestSubstring = (str) => {
//...
}
console.log(lengthOfLongestSubstring("abcabcbb"))
// 3
思路：滑动窗口法
左手从第一位a开始，右手b开始
a和b不相等
此时字符串位 ab 记max length = 2
继续右手向右移动一位
看a和c b和c是否相等（将之前所有字母和当前字母对比。）
发现都不相等
记max length = 2 此时字符串为abc
再移动一位 此时为abca
发现a重复.记录此时的字符串和长度。
当发现右手与本次的字符串有任意相等的时候就停止，
并且左手从重复的后一个开始继续上面的操作。的时候不需要右手从头指起，而是继续当前位置往后指。
max length = 后面一个的下标减去当前子字符串第一个的下标+1
如果最后一个重复则没有+1，因为最后那个重复了需要减一
max length = 后面一个的下标减去当前子字符串第一个的下标
答案：
var lengthOfLongestSubstring = (str) => {
if(str.length <= 1) return str.length
let max = 0 //最大长度
let p1 = 0 //左手0 开始 右手1开始
let p2 = 1
while(p2<str.length){
let sameIndex = -1 //和p2相同的索引
for(let i = p1;i<p2;i++){
if(str[i]===str[p2]){
sameIndex = i
break //重复了就先跳出循环计算一下长度
}
}
let tempMax
if(sameIndex != -1){
tempMax = p2-p1
p1 = sameIndex+1
}else{
tempMax = p2-p1+1
}
if(tempMax>max){
max= tempMax
}
p2+=1
}
return max
}
