2025.8.15

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

题目

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

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

总体思路

用布尔数组的滑动窗口法

• 使用固定大小数组标记字符是否出现过：
  这里 visited[128] 对应 ASCII 码字符。
  true 表示该字符在当前窗口内已经出现。
• 维护滑动窗口：
  left 表示窗口左边界，right 表示窗口右边界。
  窗口 [left, right] 中保证没有重复字符。
• 遇到重复字符时移动左指针：
  如果 visited[ch] == true，说明当前字符已在窗口中。
  移动左指针 left，同时将左边字符标记清除，直到窗口中不再有重复字符。
• 更新窗口状态：
  将当前字符 ch 标记为已出现。
  更新 maxLen 为窗口长度 right-left+1。
• 时间复杂度：
  每个字符最多进出窗口一次 → O(n)
  空间复杂度 O(1)，因为固定数组大小 128。

用哈希表的滑动窗口法

• 使用哈希表记录窗口中字符出现次数：
  键是字符，值是出现次数（这里最多是 1）。
  动态维护当前窗口的字符集合。
• 维护滑动窗口的左右指针：
  i 是左指针，rk 是右指针。
  左指针每移动一次，移除窗口最左边的字符。
  右指针尽可能右移，保证窗口内没有重复字符。
• 右指针移动条件：
  rk+1 < n 防止越界
  m[s[rk+1]] == 0 窗口中没有重复字符
  满足条件时，右指针 rk 右移，并将字符计入哈希表。
• 更新答案：
  窗口 [i, rk] 是以 i 为左边界的最长无重复字符子串
  ans = max(ans, rk-i+1)。
• 时间复杂度：
  每个字符进出窗口一次 → O(n)
  空间复杂度 O(min(n, charset))，因为哈希表动态存储字符。

代码

golang

// 使用滑动窗口法查找无重复字符的最长子串长度
func lengthOfLongestSubstring(s string) int {visited := [128]bool{} // ASCII 码范围的字符标记数组left, maxLen := 0, 0for right := 0; right < len(s); right++ {ch := s[right]// 如果当前字符已经在窗口内出现过，则移动左指针直到移除该字符for visited[ch] {visited[s[left]] = falseleft++}// 标记该字符已出现visited[ch] = true// 更新最大长度if right-left+1 > maxLen {maxLen = right - left + 1}}return maxLen
}func lengthOfLongestSubstring(s string) int {// 哈希表，记录窗口中字符出现次数m := map[byte]int{}n := len(s) // 字符串长度// 右指针，初始值为 -1// 相当于在字符串左边界左侧，还没有开始移动rk, ans := -1, 0// 遍历每个字符，i 是左指针for i := 0; i < n; i++ {if i != 0 {// 左指针向右移动一格// 移除窗口最左边的字符delete(m, s[i-1])}// 不断向右移动右指针 rk// 条件：// 1. rk+1 < n，防止越界// 2. m[s[rk+1]] == 0，窗口中没有重复字符for rk+1 < n && m[s[rk+1]] == 0 {rk++              // 右指针右移一格m[s[rk]]++        // 把该字符加入窗口}// 此时窗口 [i, rk] 是一个最长无重复字符子串// 更新答案ans = max(ans, rk-i+1)}return ans
}

---

1.两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

总体思路

暴力求解法

• 枚举所有可能的两个数：
  用两层 for 循环，第一层遍历第一个数 nums[i]，第二层遍历第二个数 nums[j]。
• 检查是否满足条件：
  如果 nums[i] + nums[j] == target 并且 i != j，说明找到了一对符合条件的下标。
• 立即返回结果：
  直接返回这两个下标 [i, j]。
• 时间复杂度：
  外层循环 O(n)，内层循环 O(n) → 总体 O(n²)。
  空间复杂度 O(1)，因为没有额外的数据结构。

哈希表优化法

• 使用哈希表记录已访问过的数值：
  建一个 map[int]int，键是数值，值是该数值在 nums 中的下标。
• 单次遍历寻找匹配：
  遍历 nums 时，对于当前数 num，计算它的“互补数” target - num。
• 检查互补数是否已出现过：
  如果互补数在哈希表中，说明之前某个元素的值 + 当前值正好等于 target，直接返回这两个下标。
• 否则记录当前数：
  把当前的 (数值 → 下标) 存进哈希表，供后续元素匹配。
• 时间复杂度：
  仅需单次遍历 O(n)。
  空间复杂度 O(n)，用来存储哈希表。

代码

golang

//暴力求解
func twoSum(nums []int, target int) []int {for i:=0;i<len(nums);i++{for j:=1;j<len(nums);j++{if nums[i]+nums[j]==target && i!=j{return []int{i,j}}}}return nil
} //哈希
func twoSum(nums []int, target int) []int {hash:=map[int]int{}   //键为“某个数值”，值为“该数值在 nums 中的下标”。for i, num:=range nums {   //range 遍历切片，i 是下标，num 是当前元素的拷贝if p, ok :=hash[target-num];ok{   //互补数是否已经出现过。如果出现过，ok == true，p 是互补数的下标。return []int{p,i}}hash[num]=i   //把“当前数值 → 当前下标”记进表里，供后面的元素来匹配。}return nil
}

---

2025.8.16

15. 三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

总体思路

双指针法

• 排序
  先对数组 nums 排序。
  排序后可以利用双指针移动来快速缩小范围。
• 固定第一个数 nums[i]
  从左到右依次枚举 i。
  如果 nums[i] > 0，因为数组已经排序，后面的数都 ≥0，不可能再凑出 0，可以直接停止。
  如果 nums[i] 跟前一个数相同，就跳过，避免重复解。
• 左右指针搜索另外两个数
  设定 left := i+1，right := n-1。
  计算三数之和 sum := nums[i] + nums[left] + nums[right]。
  • 如果 sum == 0，说明找到一组解。
    保存三元组 [nums[i], nums[left], nums[right]]。
    然后移动 left++ 和 right–，并且跳过重复值。
  • 如果 sum < 0，说明和太小，需要增大和 → left++。
  • 如果 sum > 0，说明和太大，需要减小和 → right–。
• 继续枚举下一个 i
  直到遍历完成，返回所有解。

暴力求解（三重循环）

• 枚举所有三元组
  用三层循环，依次固定下标 i、j、k，保证它们互不相等。
  枚举所有可能的组合 (nums[i], nums[j], nums[k])。
• 判断和是否为 0
  如果 nums[i] + nums[j] + nums[k] == 0，就认为它是一个符合要求的三元组。
• 避免重复
  直接三重循环会出现重复解，比如 [−1,0,1] 可能通过不同的下标组合出现多次。
  常见做法是：
  • 先对数组排序。
  • 再用一个 map 或 set（在 Go 里用 map[[3]int]bool）来记录已经出现过的三元组。
• 保存结果:
  把符合条件的三元组存入结果切片 [][]int，最后返回。

代码

golang

//双指针
import "sort"
func threeSum(nums []int) [][]int {sort.Ints(nums)  //排序n := len(nums)//left, right := 1, len(nums)-1ret := make([][]int, 0)seen := make(map[[3]int]bool)for i:=0; i<n-2; i++ {// 如果 nums[i] > 0，后面全是非负数，不可能和为0，直接breakif nums[i] > 0 {break}// 跳过重复的i，避免结果重复if i > 0 && nums[i] == nums[i-1] {continue}left, right := i+1, n-1for left<right {sum := nums[i] + nums[left] + nums[right]if sum == 0 {key:=[3]int{nums[i],nums[left],nums[right]}if !seen[key] {seen[key]=trueret = append(ret,[]int{nums[i],nums[left],nums[right]})}left++right--}else if sum < 0 {left++ // 和偏小，左指针右移} else {right-- // 和偏大，右指针左移}}}return ret}//暴力求解超时了。。。bunengyong
import "sort"
func threeSum(nums []int) [][]int {sort.Ints(nums)    //先排序，便于存入集合时用有序三元组作为去重键res := make([][]int, 0)// 使用 map 记录已经出现过的三元组（用固定顺序的[3]int作为key）seen :=make(map[[3]int]bool)for i:=0;i<len(nums)-2;i++ {for j:=i+1;j<len(nums)-1;j++ {for k:=j+1;k<len(nums);k++ {if(nums[i]+nums[j]+nums[k]==0){key := [3]int{nums[i],nums[j],nums[k]}//去重if !seen[key]{   seen[key]=trueres = append(res, []int{nums[i], nums[j], nums[k]})}}}}}return res
}