【LeetCode每日一題】

每日一題

3. 無重復字符的最長子串
- 題目
- 總體思路
- 代碼
1.兩數之和
- 題目
- 總體思路
- 代碼
15. 三數之和
- 題目
- 總體思路
- 代碼

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(n2)。
空間復雜度 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
}