#LeetCode
#滑动窗口算法
滑动窗口算法主要用于解决数组/字符串的子元素问题。可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。
其主要过程是：维护一个队列或者两个指针，通过队列出队/入队或者左右两个指针的往右移动，使窗口不断向右滑动，直到最右面为止。
用到该算法的有：
#1. 两数之和
在数组中找到2个数之和等于给定值的数字，结果返回2个数字在数组中的下标。例如：
1const nums = [2, 7, 11, 15]
2const target = 9
3
4// [0, 1]解题思路：
此题其实和数组去重类似，都是查询一个值是否在数组里去重是值本身，而此题是和target之差。
一开始想到的方式，是双指针循环两次，算法复杂度为O(n2)：
1function twoSum(nums, target){
2 const {length} = nums
3 let j = length - 1
4 let i
5 let isFind = false
6 while(!isFind && j){
7 const end = nums[j]
8
9 for (i = 0; i < j; i++) {
10 const item = nums[i];
11
12 if(item + end === target){
13 isFind = true
14
15 break
16 }
17 }
18
19 if(isFind) break
20
21 j--
22 }
23
24 return isFind ? [i, j] : null
25}深入思考后，其实与数组去重类似，可以用空间换时间，时间复杂度为O(n)：
1function twoSum(nums, target){
2 const {length} = nums
3 const map = {}
4
5 for (let index = 0; index < length; index++) {
6 const item = nums[index]
7 const diff = target - item
8 const diffIndex = map[diff]
9
10 if(diffIndex !== undefined){
11 return [diffIndex, index]
12 }else{
13 map[item] = index
14 }
15 }
16
17 return null
18}#2. 两数相加
两个非空的链表，表示两个非负的整数。每位数字逆序存储的，且每个节点只存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
1function ListNode(val, next) {
2 this.val = (val === undefined ? 0 : val)
3 this.next = (next === undefined ? null : next)
4}
5
6function addTwoNumbers(l1, l2) {
7 let isCarry = 0
8 let first, current
9
10 while (l1 || l2 || isCarry) {
11 const value1 = l1 ? l1.val : 0
12 const value2 = l2 ? l2.val : 0
13 let sum = value1 + value2 + isCarry
14
15 if (sum >= 10) {
16 isCarry = 1
17 sum = sum % 10
18 } else {
19 isCarry = 0
20 }
21
22 if (!first){
23 first = new ListNode(sum)
24 current = first
25 }else{
26 current.next = new ListNode(sum)
27 current = current.next
28 }
29
30 l1 = l1 && l1.next
31 l2 = l2 && l2.next
32 }
33
34 return first
35}#3. 无重复字符的最长子串
题目： 在一个字符串中寻找没有重复字母的最长子串
1function lengthOfLongestSubstring(s){
2 let left = 0
3 let right = 0
4 let maxLength = 0
5 const {length} = s
6
7 while (right < length) {
8 right ++
9 let sub = s.substring(left, right)
10 while(hasRepeted(sub)){
11 left++
12 sub = s.substring(left, right)
13 }
14
15 const subLength = sub.length
16 if(subLength > maxLength) maxLength = subLength
17 }
18
19 return maxLength
20}
21
22function hasRepeted(str){
23 const set = new Set()
24 const {length} = str
25 let result = false
26
27 for (let index = 0; index < length; index++) {
28 const char = str.charAt(index)
29
30 if(set.has(char)){
31 result = true
32 break
33 }
34
35 set.add(char)
36 }
37
38 return result
39}#12. 整数转罗马数字
题目：
罗马数字包含以下七种字符：I、V、X、L、C、D和M。
| 符号 | 十进制对应的值 |
|---|---|
I | 1 |
V | 5 |
X | 10 |
L | 50 |
C | 100 |
D | 500 |
M | 1000 |
例如，罗马数字2写做II，即为两个并列的1。12写做XII，即为X + II。27写做XXVII，即为XX + V + II。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如4不写做IIII，而是IV。数字1在数字5的左边，所表示的数等于大数5减小数1得到的数值4。同样地，数字9表示为IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5)和X(10)的左边，来表示4和9。
X可以放在L(50)和C(100)的左边，来表示40和90。
C可以放在D(500)和M(1000)的左边，来表示400和900。
给定一个整数，将其转为罗马数字。输入确保在1到3999的范围内。
1function intToRoman(int) {
2 const list = [{
3 roman: 'M',
4 value: 1000,
5 }, {
6 roman: 'D',
7 value: 500,
8 }, {
9 roman: 'C',
10 value: 100,
11 }, {
12 roman: 'L',
13 value: 50,
14 }, {
15 roman: 'X',
16 value: 10,
17 }, {
18 roman: 'V',
19 value: 5,
20 }, {
21 roman: 'I',
22 value: 1,
23 }]
24 let rest = int
25 let isConvertNine = false
26
27 return list.reduce( (result, item, index) => {
28 const {
29 roman,
30 value,
31 } = item
32 const next = list[index + 1]
33 const prev = list[index - 1]
34 const ten = list[index - 2]
35 let current = Math.floor(rest / value)
36
37 if (!current) return result
38
39 rest = rest % value
40
41 switch (true) {
42 case current === 1 && next && Math.floor(rest / next.value) === 4: // 9 需要特殊表示为prev + next
43 isConvertNine = true
44 break;
45 case isConvertNine && current === 4: // 说明值为9或者其倍数
46 result += roman + ten.roman
47 isConvertNine = false
48 break;
49 case !isConvertNine && current === 4: // 说明值为4
50 result += roman + prev.roman
51 break;
52 default:
53 while (current) {
54 result += roman
55 current--
56 }
57 break;
58 }
59
60 return result
61 }, '')
62}#13. 罗马数字转整数
1function romanToInt(roman) {
2 const map = {
3 I: 1,
4 V: 5,
5 X: 10,
6 L: 50,
7 C: 100,
8 D: 500,
9 M: 1000
10 }
11 const romanArr = roman.split('')
12
13 return romanArr.reduce((result, item, index) => {
14 const value = map[item]
15 const next = romanArr[index + 1]
16
17 if (!next) return result + value
18 const nextValue = map[next]
19
20 return value < nextValue ? result - value : result + value
21 }, 0)
22}#74. 合并区间
题目： 以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
解析：
关键需要先对intervals进行排序，再从左到右遍历，合并重叠区间。
否则用两次循环比较所有区间，效率会比较低。
1function merge(intervals) {
2 intervals.sort((a, b) => a[0] - b[0])
3
4 let i = 0, j = 1, result = []
5
6 while(i < intervals.length){
7 const merged = [...intervals[i]]
8 let next = intervals[j]
9
10 while(j < intervals.length && next[0] <= merged[1]){
11 merged[1] = Math.max(merged[1], next[1])
12 j++
13 next = intervals[j]
14 }
15 result.push(merged)
16 i = j
17 }
18
19 return result
20}#76. 最小覆盖子串
题目： 给两个个字符串s和t。返回s中涵盖t所有字符的最小子串。如果不存在则返回空字符串""。
1function minWindow(s, t) {
2 const {length} = s
3 const total = t.length
4 const leftSteps = getContainedSteps(s, t)
5 const rightSteps = leftSteps.slice(0)
6 let left = leftSteps.shift()
7 let right = rightSteps.shift()
8 let minSubStr = ''
9 const sourceCountMap = {}
10 const targetCountMap = getCountMap(t)
11
12 while (right <= length) {
13 let rightChat = s.charAt(right)
14 let leftChat = s.charAt(left)
15 updateCountMap(sourceCountMap, rightChat)
16
17 while (right - left >= total && sourceCountMap[leftChat] > targetCountMap[leftChat]) {
18 reduceCountMap(sourceCountMap, leftChat)
19 left = leftSteps.shift()
20 leftChat = s.charAt(left)
21 }
22
23 const subStr = s.substring(left, right + 1)
24
25 if ((!minSubStr || minSubStr.length > subStr.length) && hasContainedSource(sourceCountMap, targetCountMap)) minSubStr = subStr
26
27 if (rightSteps.length){
28 right = rightSteps.shift()
29 }else {
30 right++
31 }
32
33 }
34
35 return minSubStr
36}
37
38function getContainedSteps(source, target) {
39 const steps = []
40 const {length} = source
41
42 for (let index = 0; index < length; index++) {
43 const char = source.charAt(index)
44
45 if (target.indexOf(char) > -1) steps.push(index)
46 }
47
48 return steps
49}
50
51function getCountMap(str) {
52 const map = {}
53 const {
54 length
55 } = str
56
57 for (let index = 0; index < length; index++) {
58 const char = str.charAt(index)
59
60 updateCountMap(map, char)
61 }
62
63 return map
64}
65
66function updateCountMap(map, char) {
67 map[char] = (map[char] || 0) + 1
68}
69function reduceCountMap(map, char) {
70 map[char] = map[char] > 0 ? map[char] - 1 : 0
71}
72
73function hasContainedSource(sourceCountMap, targetCountMap) {
74 let hasContained = true
75 for (const key in targetCountMap) {
76 if (Object.hasOwnProperty.call(targetCountMap, key)) {
77 const sourceCount = sourceCountMap[key] || 0
78 if (sourceCount < targetCountMap[key]){
79 hasContained = false
80 break
81 }
82
83 }
84 }
85
86 return hasContained
87}ON THIS PAGE