BetaThis is a live doc! Anyone with edit access can make updates in real time without having to publish.
In progress
滑动窗口
LC 219. Contains Duplicate II 存在重复元素 II
https://leetcode.com/problems/contains-duplicate-ii/description/
暴力解法(TLE)
func containsNearbyDuplicate(nums []int, k int) bool { for i, v := range nums { for j := max(i-k, 0); j <= min(i+k, len(nums)-1); j++ { if i != j && nums[j] == v { return true } } } return false }
滑动窗口
func containsNearbyDuplicate(nums []int, k int) bool { left, right := 0, 0 window := make(map[int]bool, len(nums)) for right < len(nums) { if window[nums[right]] { return true } window[nums[right]] = true right++ if right - left > k { window[nums[left]] = false left++ } } return false }
LC 209. Minimum Size Subarray Sum 长度最小的子数组
https://leetcode.com/problems/minimum-size-subarray-sum/description/
func minSubArrayLen(target int, nums []int) int { left, right := 0, 0 sum := 0 minLength := math.MaxInt for right < len(nums) { sum += nums[right] right++ for sum >= target && left < right { minLength = min(minLength, right-left) sum -= nums[left] left++ } } if minLength == math.MaxInt { return 0 } return minLength }
LC 395. Longest Substring with At Least K Repeating Characters 至少有 K 个重复字符的最长子串
https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/
func longestSubstring(s string, k int) int { l := 0 for i := 1; i <= 26; i++ { l = max(l, longestSubstringWithCount(s, k, i)) } return l } func longestSubstringWithCount(s string, k int, count int) int { left, right := 0, 0 window := make([]int, 26) maxLength := 0 for right < len(s) { window[id(s[right])]++ right++ for countForExists(window) > count { window[id(s[left])]-- left++ } if countForTarget(window, k) == count { maxLength = max(maxLength, right - left) } } return maxLength } func id(c byte) int { return int(c - 'a') } func countForExists(w []int) (c int) { for _, v := range w { if v > 0 { c++ } } return c } func countForTarget(w []int, k int) (c int){ for _, v := range w { if v >= k { c++ } } return c }
复习
LC 15. 3Sum 三数之和
https://leetcode.com/problems/3sum/
func threeSum(nums []int) (results [][]int) { sort.Ints(nums) k := 0 for k < len(nums) { partResults := twoSum(nums[k+1:], -nums[k]) for _, r := range partResults { results = append(results, append([]int{nums[k]}, r...), ) } for v := nums[k]; k < len(nums) && nums[k] == v; k++ {} } return } func twoSum(nums []int, target int) (results [][]int) { i, j := 0, len(nums)-1 for i < j { sum := nums[i] + nums[j] if sum == target { results = append(results, []int{nums[i], nums[j]}) for v := nums[i]; i < len(nums) && nums[i] == v; i++ {} for v := nums[j]; j >= 0 && nums[j] == v; j-- {} } else if sum < target { for v := nums[i]; i < len(nums) && nums[i] == v; i++ {} } else { for v := nums[j]; j >= 0 && nums[j] == v; j-- {} } } return }
LC 18. 4Sum 四数之和
func fourSum(nums []int, target int) (results [][]int) { sort.Ints(nums) i := 0 for i < len(nums) - 3 { j := len(nums) - 1 for i + 2 < j { partResults := twoSum(nums[i+1:j], target-(nums[i]+nums[j])) for _, r := range partResults { results = append(results, []int{nums[i], r[0], r[1], nums[j]}, ) } for v := nums[j]; j > i+2 && nums[j] == v; j-- {} } for v := nums[i]; i < len(nums)-3 && nums[i] == v; i++ {} } return } func twoSum(nums []int, target int) (results [][]int) { i, j := 0, len(nums)-1 for i < j { sum := nums[i] + nums[j] if sum == target { results = append(results, []int{nums[i], nums[j]}) for v := nums[i]; i < len(nums) && nums[i] == v; i++ {} for v := nums[j]; j >= 0 && nums[j] == v; j-- {} } else if sum < target { for v := nums[i]; i < len(nums) && nums[i] == v; i++ {} } else { for v := nums[j]; j >= 0 && nums[j] == v; j-- {} } } return }
LC 46. Permutations 全排列
https://leetcode.com/problems/permutations
func permute(nums []int) (result [][]int) { backtrack(&result, nums, make([]int, 0, len(nums)), make(map[int]bool, len(nums))) return } func backtrack(result *[][]int, nums []int, current []int, used map[int]bool) { if len(current) == len(nums) { *result = append(*result, append([]int(nil), current...)) return } for _, num := range nums { if used[num] { continue } current = append(current, num) used[num] = true backtrack(result, nums, current, used) current = current[:len(current)-1] used[num] = false } }