## 209. 长度最小的子数组

#同向双指针 #滑动窗口 

[209. 长度最小的子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)


```java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = n + 1; // 用于比较min值，所以需要是n+1
        int s = 0; // 用于计算从left到right的数组和
        int l = 0; // 左指针
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            s += x;
            // 如果num[r]是大于target的，将左指针右移缩小范围
            while (s >= target) {
                // 更新答案
                ans = Math.min(ans, r - l + 1);// r-l+1 计算的是子数组的长度，需要加1
                s -= nums[l]; // 减去左边的值
                l++; // 移动指针
            }
        }
        // 如果循环结束后ans还是等于n+1则相当于没有答案返回0
        if (ans == n + 1) {
            return 0;
        } else {
            return ans;
        }
    }
}
```

**复杂度分析**
- 时间复杂度：$O(n)$，对于本题，虽然有两层循环，但是 $l$ 至多可以加 $n$ 次，而不是一般双层循环的可以加 $n^2$ 次，所以是 $O(n)$
- 空间复杂度：$O(1)$，没有使用额外变量数组之类的，故为 $O(1)$

## 713. 乘积小于 K 的子数组

#同向双指针 #滑动窗口 

[713. 乘积小于 K 的子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/subarray-product-less-than-k/description/)

```java
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // 判断k是否小于1
        if (k <= 1) {
            return 0;
        }
        int n = nums.length;
        int ans = 0;
        float prod = 1; // 用于计算从left到right的数组和
        int l = 0; // 左指针
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            prod *= x;
            // 如果num[r]是大于target的，将左指针右移缩小范围
            while (prod >= k) {
                // 更新答案
                prod /= nums[l]; // 减去左边的值
                l++; // 移动指针
            }
            ans += r - l + 1;
        }
        return ans;
    }
}
```

**复杂度分析**
- 时间复杂度: $O(n)$
- 空间复杂度：$O(1)$


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

#同向双指针 #滑动窗口

[3. 无重复字符的最长子串 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/)

```java
import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int n = s.length();
        Map<String, Integer> cnt = new HashMap<>();
        int l = 0;
        for (int r = 0; r < n; r++) {
            String rKey = String.valueOf(s.charAt(r));
            cnt.put(rKey, cnt.getOrDefault(rKey, 0) + 1); // 遍历过一个字符，则在哈希表中记录下来
            // ==2说明遇到相同的字符了
            while (cnt.get(rKey) == 2) {
                String lKey = String.valueOf(s.charAt(l));
                cnt.put(lKey, cnt.getOrDefault(lKey, 0) - 1); // 让其左端点减1
                l++;
            }
            ans = Math.max(ans, r - l + 1); // 统计碰到的最大子串长度
        }
        return ans;
    }
}
```

使用 Java 包装类 HashMap 实现性能不是最优，可考虑 ASCII 字符只有128个，构建一个128字符数组记录字符出现字符即可

```java
import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int n = s.length();
        int[] lastIndex = new int[128]; // 存储ASCII字符(128)个，数组的每个值表示字符出现次数
        Arrays.fill(lastIndex, -1); // 初始化数组的每个值都为-1
        int l = 0;
        for (int r = 0; r < n; r++) {
            char c = s.charAt(r);
            l = Math.max(l, lastIndex[c] + 1); // 移动到该字符出现次数的下一个位置
            ans = Math.max(ans, r - l + 1); // 这样就得到了一段无重复字符的字符串 r-l+1是字符串的长度
            lastIndex[c] = r; // 记录字符位置
        }
        return ans;
    }
}
```

这样耗时和内存占用就更小了

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/7c2be47c65068a833aabec7d5f0b6908.png)

**复杂度分析**
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$，字符总共只能出现128个，所以并不是 n，而 cnt 就不会是 n 的复杂度



## 2958. 最多 K 个重复元素的最长子数组

#同向双指针 #滑动窗口 

[2958. 最多 K 个重复元素的最长子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/length-of-longest-subarray-with-at-most-k-frequency/description/)

```java
import java.util.*;

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        int l = 0;
        // 创建一个数组，记录数字的出现次数
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            // 遍历数字一次，将其加1
            cnt.merge(x, 1, Integer::sum);
            while (cnt.get(x) > k) {
                int y = nums[l];
                cnt.merge(y, -1, Integer::sum);
                l++;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
```

**复杂度分析**
- 时间复杂度：$O(n)$，同向双指针的共同点
- 空间复杂度：$O(n)$，使用了一个 HashMap 存储数字出现次数

## 2730. 找到最长的半重复子字符串

#相向双指针 #滑动窗口 

[2730. 找到最长的半重复子字符串 - 力扣（LeetCode）](https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/description/)

```java
class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        // 转换为字符数组
        char[] ch = s.toCharArray();
        int n = s.length();
        int ans = 1;
        int l = 0;
        int same = 0;
        for (int r = 1; r < n; r++) {
            // 需要比较与前一个数是否相同
            if (ch[r] == ch[r - 1]) {
                same++;
            }
            // 表示出现了两次
            if (same > 1) {
                l++;
                while (ch[l] != ch[l - 1]) {
                    l++;
                }
                same = 1;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
```

**复杂度分析**
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$，使用了 ch 存储将字符串 s 转换为字符数组的变量，直接使用 String 的 charAt 即可减少空间复杂度

2024-4-25 力扣刷题记录

Redis面试题

2024-4-24 力扣刷题记录

浏览器中常见的过期存储方式为 Cookie 。Cookie 可以设置存储内容的过期时间、立即过期等等，但是 Cookie 的大小限制为 4KB（4096字节）。这是指整个 Cookie（包括名称、值、过期时间、路径、域等信息）的总大小不能超过 4KB。如果你使用的是 Cookie 登录的方式，那么 Cookie 中的内容将自动携带进后端需要 Cookie 的请求头中，这非常不友好，于是，我设计了如下这种方式的自动过期方案的 localStorage 持久化

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/4815cd16c0853aac1553936719a3b69a.png)

1. 这是原来的方案，非常不友好
```ts
export function getExpiredStorage(storage: Storage, expiresTime: string | number | Date) {
	return {  
	  getItem(key: string) {  
	    // pinia 的持久化插件要求返回字符串  
	    return JSON.stringify(storage.get(key))  
	  },  
	  setItem(key: string, value: string) {  
	    console.log('storage.set(key, value)', key, value)  
	    storage.set(key, value, expiresTime)  
	  },  
	  removeItem(key: string) {  
	    storage.remove(key)  
	  },  
	  clear() {  
	    storage.keys().forEach((key: any) => {  
	      storage.remove(key)  
	    })  
	  },  
	  key(index: number): string | null {  
	    return storage.keys()[index] || null  
	  },  
	  length: storage.keys().length,  
	} as Storage
}

const { cookies } = useCookies()  
  
const expiresTime = 60 * 30 // 自定义过期时间 30 分钟  
const expiredStorage = getExpiredStorage(cookies, expiresTime)

export const useUserStore = defineStore(
	'userStore',  
	() => {
		// 略
	},
	{  
	  persist: {  
	    storage: expiredStorage,  
	    debug: true,  
	  },  
	},
)
```

2. 通过将过期时间戳带入存储的数据中，实现过期自动清除数据，这里还可以做加密，等等

```ts
export function getExpiredStorage(storage: Storage, expiresTime: string | number | Date) {  
  return {  
    getItem(key: string) {  
      const itemStr = storage.getItem(key)  
      if (!itemStr) {  
        return null  
      }  
      // 读取的时候是字符串，需要转换为对象  
      const item = JSON.parse(itemStr)  
      const now = new Date()  
      if (now.getTime() > item.expiry) {  
        storage.removeItem(key)  
        return null  
      }  
      // pinia 的持久化插件要求返回JSON字符串  
      return JSON.stringify(item.value)  
    },  
    setItem(key: string, value: string) {  
      const now = new Date()  
      const item = {  
        value: JSON.parse(value), // value是JSON字符串，需要转换为对象  
        expiry: now.getTime() + Number(expiresTime) * 1000,  
      }  
      storage.setItem(key, JSON.stringify(item)) // 存储又要转为JSON字符串  
    },  
    removeItem(key: string) {  
      storage.removeItem(key)  
    },  
    clear() {  
      Object.keys(storage).forEach((key: string) => {  
        storage.removeItem(key)  
      })  
    },  
    key(index: number): string | null {  
      const keys = Object.keys(storage)  
      return keys[index] || null  
    },  
    length: Object.keys(storage).length,  
  } as Storage  
}

const expiresTime = 60 * 30 // 自定义过期时间 30 分钟
const expiredStorage = getExpiredStorage(localStorage, expiresTime)

export const useUserStore = defineStore(
	'userStore',  
	() => {
		// 略
	},
	{  
	  persist: {  
	    storage: expiredStorage,  
	    debug: true,  
	  },  
	},
)
```

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/42d23f054f105bb1a9247b74b73fc1d0.png)

这个数据在30分钟后再次读取将自动清除

创建一个自定义过期时间的持久化 Pinia (Vue 菠萝)

![image-20240408100632322](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/faa0c475c4c05443843d740aa7af871f.png)

后端使用cookie记录登录信息时，登录完成后响应头会携带Set-Cookie属性，浏览器会识别Set-Cookie并在满足一些条件后将Cookie注入浏览器中。

这里的请求它如果是跨域（前端域名和后端域名不一致）的，那么Cookie将无法注入。

## 1 前端设置

跨域请求的情况下，浏览器默认禁止携带cookie，如果想携带cookie，需要在请求时设置`withCredentials`参数为`true`，fetch请求的设置方法为`method.config.credentials = 'include'`

当请求的`credentials`模式为`include`时，响应头`Access-Control-Origin`的值不可以是`*`，也就是说服务端的cors插件的origin参数，必须指定具体域名，而不能是`*`这种通配符

在这个设置后的Cookie注入情况

![8559f98dc9ab4d7dc5e3a969cb213de0](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/8559f98dc9ab4d7dc5e3a969cb213de0.jpg)

## 2 后端设置

前端设置完毕后，将开始设置后端，后端主要设置`SameSite`

`SameSite`允许我们声明 cookie 可以用来 first-party 或者 same-site。它会明确的给出“网站”是指哪些（哪些可以带 cookie）。网站由域名后缀和域名前部分组成，比如`www.web.dev`是`web.dev`的一部分。

`SameSite`属性提供了三种不同的方式来管理 cookie，你可以不指定这个属性（`None`），或者使用`Strict`和`Lax`来限制 cookie 的 same-site 请求。

**Strict**

`Strict`最为严格，完全禁止第三方 Cookie，跨站点时，任何情况下都不会发送 Cookie。换言之，只有当前网页的 URL 与请求目标一致，才会带上 Cookie。

这个规则过于严格，可能造成非常不好的用户体验。比如，当前网页有一个 GitHub 链接，用户点击跳转就不会带有 GitHub 的 Cookie，跳转过去总是未登陆状态。

**Lax**

`Lax`规则稍稍放宽，大多数情况也是不发送第三方 Cookie，但是导航到目标网址的 Get 请求除外。

导航到目标网址的 GET 请求，只包括三种情况：链接，预加载请求，GET 表单。详见下表。

| 请求类型  |                 示例                 |    正常情况 | Lax         |
| :-------- | :----------------------------------: | ----------: | :---------- |
| 链接      |         `<a href="..."></a>`         | 发送 Cookie | 发送 Cookie |
| 预加载    | `<link rel="prerender" href="..."/>` | 发送 Cookie | 发送 Cookie |
| GET 表单  |  `<form method="GET" action="...">`  | 发送 Cookie | 发送 Cookie |
| POST 表单 | `<form method="POST" action="...">`  | 发送 Cookie | 不发送      |
| iframe    |    `<iframe src="..."></iframe>`     | 发送 Cookie | 不发送      |
| AJAX      |            `$.get("...")`            | 发送 Cookie | 不发送      |
| Image     |          `<img src="...">`           | 发送 Cookie | 不发送      |

设置了`Strict`或`Lax`以后，基本就杜绝了 CSRF 攻击。当然，前提是用户浏览器支持 SameSite 属性。

**None**

这种情况下允许在 third-party 发送请求时使用 cookie

但是设置`SameSite`为`None`时需要同时设置`Secure`，Cookie 只能通过 HTTPS 协议发送），否则无效。

```bash
Set-Cookie: widget_session=abc123; SameSite=None; Secure
```



在我们的后端并没有设置HTTPS协议，故通过设置SameSite的方式完全无效了，我们选择通过代理的方式设置。

这块设置完后的Cookie注入情况

![ea565c6f5879015f8b07c432d14101e3](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/ea565c6f5879015f8b07c432d14101e3.jpg)

## 3 代理设置

在生产环境中，我们可以通过设置前端的Nginx代理服务器，设置后端服务反向代理到前端的域名上(或者前端反向代理到后端服务器上也是一样的)这样就从根源上解决了跨域问题。

Nginx配置如下

```nginx
# 代替vite 中的代理服务 功能 反向代理后端域名到 前端
location /api {
    proxy_pass http://xx.xx.xx.xx:xx;
    proxy_set_header Host $host;
    proxy_set_header X-Real-IP $remote_addr;
    proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
}
```

这个时候，请求前端域名`http://localhost:5173/api`就相当于请求后端域名的`http://xx.xx.xx.xx:xx/api`，注意Nginx是没有重写功能的，故必须配置后端的请求路径

```yaml
servlet:
    context-path: /api
```

这个时候就可以正常的注入Cookie了

开发环境中的前端配置，需要通过 Vite 的代理服务器实现，具体配置如下，基本都会的

```js
server: {  
  // 指定dev sever的端口号，默认为5173  
  port: env.VITE_APP_PORT,  
  // 自动打开浏览器运行以下页面  
  // open: '/',  
  // 设置反向代理  
  proxy: {  
    // 以下示例表示：请求URL中含有"/api"，则反向代理到http://localhost  
    // 例如: http://localhost:3000/api/login -> http://localhost/api/login  
    // 如果反向代理到localhost报错Error: connect ECONNREFUSED ::1:80，  
    // 则将localhost改127.0.0.1  
    '/api': {  
      target: env.VITE_API_URL,  
      changeOrigin: true,  
      // rewrite: (path) => path.replace(/^\/api/, ''),  
    },  
  },  
},
```