https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked
没做出来
这题比较鸡贼
利用了前缀和以及hash
以末尾点为判断来看前边有多少种
```js
var subarraySum = function (nums, k) {
const numMap = new Map()
let result = 0
let sum = 0
numMap.set(0, 1)
for (const num of nums) {
sum += num
if (numMap.has(sum - k)) {
result+=numMap.get(sum-k)
}
if (numMap.has(sum)) {
numMap.set(sum, numMap.get(sum) + 1)
}else{
numMap.set(sum, 1)
}
}
return result
};
```
https://leetcode.cn/problems/sliding-window-maximum/submissions/557702437/?envType=study-plan-v2&envId=top-100-liked
想拿单调栈解来着
他妈写反判断了...
```js
var maxSlidingWindow = function (nums, k) {
const stack = []
const ans = []
for (let index = 0; index < k; index++) {
const num = nums;
while (num > nums]) {
stack.pop()
}
stack.push(index)
}
ans.push(nums])
for (let index = k; index < nums.length; index++) {
const num = nums;
while (num > nums]) {
stack.pop()
}
while(stack<=index-k||nums]<=num){
stack.shift()
}
stack.push(index)
ans.push(nums])
}
return ans;
};
```
大小堆的解就不提了
解法3是真的天才
!(data/attachment/forum/202408/22/181207jk6sh6rog3h8hofk.png)
https://leetcode.cn/problems/minimum-window-substring/submissions/557713308/?envType=study-plan-v2&envId=top-100-liked
差一点
边界太多了...
没憋出来
```js
var minWindow = function (s, t) {
const typeMap = new Map()
let tpyeNum = 0
for (let index = 0; index < t.length; index++) {
const char = t;
if (typeMap.has(char)) {
typeMap.set(char, typeMap.get(char) + 1)
} else {
typeMap.set(char, 1)
tpyeNum++;
}
}
let left = -1
let right = -1
let result=""
for (let index = 0; index < s.length; index++) {
const char = s;
right++
if (typeMap.has(char)) {
typeMap.set(char, typeMap.get(char) - 1)
if (typeMap.get(char) == 0) {
tpyeNum--;
}
}
if (tpyeNum == 0) {
while (true) {
const char = s
if (typeMap.has(char)) {
if (typeMap.get(char) < 0) {
typeMap.set(char, typeMap.get(char) + 1)
left++;
} else if (typeMap.get(char) == 0) {
break;
}
} else {
left++;
}
}
const newResult=s.substring(left,right+1)
result=(result==""||newResult.length<result.length)?newResult:result
}
}
return result
};
```
https://leetcode.cn/problems/maximum-subarray/submissions/557728791/?envType=study-plan-v2&envId=top-100-liked
这个没思路
但是解太草了...
```js
var maxSubArray = function(nums) {
let pre = 0, maxAns = nums;
nums.forEach((x) => {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
});
return maxAns;
};
```
https://leetcode.cn/problems/merge-intervals/submissions/557733294/?envType=study-plan-v2&envId=top-100-liked
排序之后区间合并，复杂度NlogN
```js
var merge = function (intervals) {
intervals.sort((a, b) => {
return a - b
})
const result = []
for (let index = 0; index < intervals.length; index++) {
const arr = intervals;
const last = result??
if (arr>=last&&arr<=last){
last=Math.max(arr,last)
}else if (arr>=last&&arr<=last){
last=Math.max(arr,last)
}else{
result.push(arr)
}
}
return result
};
```
https://leetcode.cn/problems/rotate-array/submissions/558244872/?envType=study-plan-v2&envId=top-100-liked
只会题解1
题解2和3太神奇了
3反转还算能理解
2利用了公倍数酷酷一顿换算最后能得到环路数来进行遍历
真的牛逼
https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked
前缀和变种
easy
```js
var productExceptSelf = function (nums) {
const suffix = []
const prefix = []
for (let index = 0; index < nums.length; index++) {
const num = nums;
prefix = num * (prefix ?? 1)
}
for (let index = nums.length - 1; index >= 0; index--) {
const num = nums;
suffix = num * (suffix ?? 1)
}
const answer = []
for (let index = 0; index < suffix.length; index++) {
answer.push((prefix ?? 1) * (suffix ?? 1))
}
return answer
};
```
https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked
将数组自身做正整数的存储数组
每个数字只跳动一次
复杂度ON
```js
var firstMissingPositive = function (nums) {
for (let index = 0; index < nums.length; index++) {
let num = nums;
while (true) {
if (num <= 0 || num > nums.length) {
break;
}
const nextNum = nums
if (nextNum <= 0 || nextNum > nums.length) {
//不需要设置了
nums = num
break;
}
if (nextNum == num) {
break;
}
nums = num
num = nextNum
}
}
let minNum = 1
for (let index = 0; index < nums.length; index++) {
const num = nums;
if (minNum == num) {
minNum++
}
}
return minNum
};```
https://leetcode.cn/problems/set-matrix-zeroes/?envType=study-plan-v2&envId=top-100-liked
我本来想标记a字符...
感觉有点太取巧了，虽然比方法1强
方法2和3不太喜欢
太凹了
学了2的思路自己写了一下
```js
var setZeroes = function (matrix) {
let rowZero = false
let colZero = false
for (let index = 0; index < matrix.length; index++) {
const num = matrix
if (num === 0) {
rowZero = true
}
}
for (let index = 0; index < matrix.length; index++) {
const num = matrix
if (num === 0) {
colZero = true
}
}
for (let index = 0; index < matrix.length; index++) {
const row = matrix;
for (let indey = 0; indey < row.length; indey++) {
const num = row;
if (num === 0) {
matrix = 0
matrix = 0
}
}
}
for (let index = 1; index < matrix.length; index++) {
const row = matrix;
for (let indey = 1; indey < row.length; indey++) {
if (matrix === 0 | matrix === 0) {
matrix = 0
}
}
}
if (rowZero) {
for (let index = 0; index < matrix.length; index++) {
matrix = 0
}
}
if (colZero) {
for (let index = 0; index < matrix.length; index++) {
matrix = 0
}
}
return matrix
};
```