# 介绍

TIP

本篇开始刷 leetcode 上面的前端题目

# 1. 两数之和

# 题目

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

示例:

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

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

# 思路

  • 使用一个 map 将遍历过的数字存起来,值作为 key,下标作为值
  • 对于每一次遍历:
    1. 取 map 中查找是否有 key 为 target-nums[i]的差值
    2. 如果取到了,则条件成立,返回。
    3. 如果没有取到,将当前值作为 key,下标作为值存入 map
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

# 代码

var twoSum = function (nums, target) {
	// 1. 创建map存储元素和对应下标,也可以用{}
	const map = new Map()
	// 2. 遍历nums数组
	for (let i = 0; i < nums.length; i++) {
		// 3. 获取差值
		const diff = target - nums[i]
		// 4. 判断key是否包含差值
		if (map.has(diff)) {
			// 4.1 如果包含就返回两个下标数组
			return [map.get(diff), i]
		} else {
			// 4.2 如果没有包含就设值到map中
			map.set(nums[i], i)
		}
	}
	// 5. 如果遍历完没有找到,就返回空数组
	return []
}

# 3. 无重复字符的最长子串

# 题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

# 思路

  • 使用一个 set 将遍历过的字符存起来
  • 定义两个指针,i 和 j,i 用于遍历字符串,j 用于删除 set 中的子字符串
  • 判断 set 中是否有 s[i],即当前遍历的字符串:
    1. 没有就添加并计算长度
    2. 有的话就从移动 j,并从开始一直删除到当前元素,再将重复的元素加入到 set 中
  • 遍历完全部字符即可

# 代码

var lengthOfLongestSubstring = function (s) {
	// 1. 判断空字符
	if (s.length === 0) {
		return 0
	}

	// 2. 创建set用于记录已经遍历的字符
	const set = new Set()
	// 3. 定义两个指针和长度
	let i = 0,
		j = 0,
		maxLength = 0
	// 4. 遍历字符串
	for (i; i < s.length; i++) {
		if (!set.has(s[i])) {
			// 4.1 如果set中不存在当前字符,就添加字符到set,然后对比长度
			set.add(s[i])
			maxLength = Math.max(maxLength, set.size)
		} else {
			// 4.2 如果set中已经存在当前字符,就从开始位子一直删除到当前字符截止,然后移动指针
			while (set.has(s[i])) {
				set.delete(s[j])
				j++
			}
			// 4.3 添加当前的字符到set中,因为while中已经全部删除了
			set.add(s[i])
		}
	}
	// 5. 返回最大长度
	return maxLength
}

# 5. 最长回文子串

# 题目

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"

# 思路

  • 判断字符串长度小于 2,直接返回原字符串
  • 定义两个变量,start 保存开始位置,maxLength 记录字符串长度,终止位置为 start + maxLength
  • 创建一个 helper function
    1. 判断左右两边是否越界,同时判断左右两边字符是否相等
    2. 满足 1 就更新回文字符的起始位置和最大长度
    3. 然后 left 和 right 指针移动,一直查找不满足条件为止
  • 遍历字符串,然后每个字符分别调用 helper function 两次
    1. 第一次 i-1 和 i+1, 例如 aba
    2. 第二次 i 和 i + 1,例如 abba
  • 最后截取字符得到答案

# 代码

// 回文串的意思是:左右两边一样的字符串 abba  aba
var longestPalindrome = function (s) {
	// 1. 判断字符长度大于2直接返回s
	if (s.length < 2) {
		return s
	}

	// 2. 定义变量:开始位置和最大长度
	let start = 0
	let maxLength = 1

	// 3. 定义中心往两边扩散的方法
	function expandAroundCenter(left, right) {
		// 3.1 判断越界和持续查找
		while (left >= 0 && right < s.length && s[left] === s[right]) {
			// 3.2 如果出现更大回文更新变量值
			if (right - left + 1 > maxLength) {
				maxLength = right - left + 1
				start = left
			}
			// 3.3 往两边移动指针
			left--
			right++
		}
	}

	// 4. 遍历字符串,每个字符中心扩散两次
	for (let i = 0; i < s.length; i++) {
		// 4.1 以当前字符为中心,分别扩散左右两个字符,"aba"
		expandAroundCenter(i - 1, i + 1)
		// 4.2 以当前字符和相邻字符为中心,分别扩散左右两个字符,"abba"
		expandAroundCenter(i, i + 1)
	}

	// 5. 返回回文字符串
	return s.substring(start, start + maxLength)
}

# 5. 三数之和

# 题目

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

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

# 思路

  • 数组升序排列
  • 遍历数组,从 0 到 length - 2 的位置,-2 是为了防止越界,因为是三个数求和
  • 如果当前数字与前一个数字相同就跳过当前这个数,为了去重
  • 如果数字不同,则设置 start = i + 1,end = length - 1,然后判断三数之和与 0 的关系
    1. 等于 0,三数加入结果数组
    2. 小于 0,start++
    3. 大于 0,end--
  • 最后返回结果

# 代码

var threeSum = function (nums) {
	// 1. 定义返回结果数组
	const result = []
	// 2. 判断为空和长度
	if (nums === null || nums.length < 3) {
		return result
	}

	// 3. 排序->升序
	nums.sort((a, b) => a - b)

	// 4. 遍历nums
	let len = nums.length
	for (let i = 0; i < len - 2; i++) {
		// 4.1 第一次或者相邻两个元素不相等的时候执行(第一次去重)
		if (i === 0 || nums[i] !== nums[i - 1]) {
			// 4.2 定义开始和结束两个指针
			let start = i + 1
			let end = len - 1
			// 4.3 开始和结束指针不相等就一直查找,相等结束循环
			while (start < end) {
				// 4.4 根据求和与0的对比分情况处理
				let sum = nums[i] + nums[start] + nums[end]
				if (sum === 0) {
					// 等于0,放入元素数组,然后移动双指针
					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--
					}
				} else if (sum < 0) {
					// 小于0,往右移动开始指针
					start++
				} else {
					// 大于0,往左移动结束指针
					end--
				}
			}
		}
	}
	// 5. 返回结果数组
	return result
}

# 20. 有效的括号

# 题目

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足:

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

# 思路

  • 创建 map,放入括号配对,左括号为 key,右括号为 value
  • 创建一个 stack,for 循环字符串,判断 map 中是否有当前这个字符的 key
    1. 如果有就取出 value,放入 stack 中
    2. 如果没有就从 stack 取出栈顶元素来和当前元素对比,不符合就返回 false
  • 循环结束之后判断 stack 是否为空,不为空就返回 false,为空就返回 true

# 代码

var isValid = function (s) {
	// 1. 判断字符长度不是偶数,返回false
	if (s.length % 2 !== 0) {
		return false
	}

	// 2. 创建括号map
	const mappings = new Map()
	mappings.set("(", ")")
	mappings.set("[", "]")
	mappings.set("{", "}")

	// 3. 创建栈stack存放所有的括号
	const stack = []
	// 4. 遍历字符
	for (let i = 0; i < s.length; i++) {
		// 4.1 判断map中是否有左括号字符
		if (mappings.has(s[i])) {
			// 如果有的话就取出右边部分放入stack
			stack.push(mappings.get(s[i]))
		} else {
			// 如果没有就取出栈顶元素和当前括号对比,没有直接返回false,有就进入下一次循环
			if (stack.pop() !== s[i]) {
				return false
			}
		}
	}

	// 5. 即判断括号不配对的情况,返回false
	if (stack.length !== 0) {
		return false
	}

	// 6. 全部配对返回true
	return true
}

# 21. 合并两个有序链表

# 题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

# 思路

  • 创建 空节点
  • 遍历两个单项链表,然后判断对应的值:
    1. 当前指针指向较小值,然后往前移动指针
    2. 更新当前指针
  • 判断是否有剩余,有的话就继续链上即可

# 代码

var mergeTwoLists = function (l1, l2) {
	// 1. 创建一个新的空节点
	let curr = new ListNode()
	// 2. 用于返回
	let dummy = curr
	// 3. 遍历l1和l2两个单项链表
	while (l1 !== null && l2 !== null) {
		if (l1.val < l2.val) {
			// 3.1 l1的值小于l2的值:当前指针指向l1,然后往前移动指针
			curr.next = l1
			l1 = l1.next
		} else {
			// 3.2 l1的值大于l2的值:当前指针指向l2,然后往前移动指针
			curr.next = l2
			l2 = l2.next
		}
		// 3.3 当前指针往前移动
		curr = curr.next
	}
	// 4. 判断两个链表对比完成知乎,l1还有剩余元素
	if (l1 !== null) {
		curr.next = l1
	}
	// 5. 判断两个链表对比完成知乎,l2还有剩余元素
	if (l2 !== null) {
		curr.next = l2
	}
	// 6. 返回链表开头
	return dummy.next
}

# 49. 字母异位词分组

# 题目

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明:

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

# 思路

  • 检查是否为空数组
  • 遍历数组,按照相同字母出现的频率进行分组归类,使用 hashMap
  • 建立一个长度为 26 的数组,填充初始值为 0
  • 遍历字符串,将字母出现频率放到数组的对应位置,利用 ascii 码-97 来获取下标
  • 遍历 map,返回结果

# 代码

var groupAnagrams = function (strs) {
	// 1. 判断字符为空的情况
	if (strs.length === 0) {
		return []
	}
	// 2. 用于存储数据的map
	const map = new Map()
	// 3. 遍历字符数组
	for (const str of strs) {
		// 3.1 先创建一个英文26个字母的数组,填充0
		const characters = Array(26).fill(0)
		// 3.2 遍历每个单词字符
		for (let i = 0; i < str.length; i++) {
			// 3.3 获取字母对应的ascii码,然后-97得到数组的下标
			const ascii = str.charCodeAt(i) - 97
			// 3.4 对应数组元素加1
			characters[ascii]++
		}
		// 3.5 字符数组转化字符作为map的key
		const key = characters.join("")
		if (map.has(key)) {
			// map中已经存在就合并数组
			// map.set(key, map.get(key).push(str))
			map.set(key, [...map.get(key), str])
		} else {
			// map中不存在就添加数组
			map.set(key, [str])
		}
	}

	// 4. 遍历map,然后返回数组
	const result = []
	for (const arr of map) {
		result.push(arr[1])
	}
	return result
}