知识库

BetaThis is a live doc! Anyone with edit access can make updates in real time without having to publish.

Edited Mar 3

By Bryan

In progress

1 滑动窗口
2 复习
- 2.1 LC 15. 3Sum 三数之和
- 2.2 LC 18. 4Sum 四数之和
- 2.3 LC 46. Permutations 全排列

滑动窗口

LC 219. Contains Duplicate II 存在重复元素 II

https://leetcode.com/problems/contains-duplicate-ii/description/

暴力解法（TLE）

1func 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
10}

滑动窗口

1func 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++
10
      if right - left > k {
          window[nums[left]] = false
          left++
      }
  }
16
  return false
18}

LC 209. Minimum Size Subarray Sum 长度最小的子数组

https://leetcode.com/problems/minimum-size-subarray-sum/description/

1func minSubArrayLen(target int, nums []int) int {
  left, right := 0, 0
  sum := 0
  minLength := math.MaxInt
  for right < len(nums) {
      sum += nums[right]
      right++
8
      for sum >= target && left < right {
          minLength = min(minLength, right-left)
          sum -= nums[left]
          left++
      }
  }
15
  if minLength == math.MaxInt {
      return 0
  }
  return minLength
20}

LC 395. Longest Substring with At Least K Repeating Characters 至少有 K 个重复字符的最长子串

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/

1func longestSubstring(s string, k int) int {
2    l := 0
3    for i := 1; i <= 26; i++ {
4        l = max(l, longestSubstringWithCount(s, k, i))
5    }
6    return l
7}
8
9func longestSubstringWithCount(s string, k int, count int) int {
10    left, right := 0, 0
11    window := make([]int, 26)
12    maxLength := 0
13    for right < len(s) {
14        window[id(s[right])]++
15        right++
16
17        for countForExists(window) > count {
18            window[id(s[left])]--
19            left++
20        }
21
22        if countForTarget(window, k) == count {
23            maxLength = max(maxLength, right - left)
24        }
25    }
26    return maxLength
27}
28
29func id(c byte) int {
30    return int(c - 'a')
31}
32
33func countForExists(w []int) (c int) {
34    for _, v := range w {
35        if v > 0 {
36            c++
37        }
38    }
39    return c
40}
41
42func countForTarget(w []int, k int) (c int){
43    for _, v := range w {
44        if v >= k {
45            c++
46        }
47    }
48    return c
49}

复习

LC 15. 3Sum 三数之和

https://leetcode.com/problems/3sum/

1func threeSum(nums []int) (results [][]int) {
  sort.Ints(nums)
3
  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...),
          )
      }
12
      for v := nums[k]; k < len(nums) && nums[k] == v; k++ {}
  }
  
  return
17}
18
19func 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]})
25
          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 
35}

LC 18. 4Sum 四数之和

1func fourSum(nums []int, target int) (results [][]int) {
  sort.Ints(nums)
3
  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++ {}
  }
18
  return
20}
21
22func 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]})
28
          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
38}

LC 46. Permutations 全排列

https://leetcode.com/problems/permutations

1func permute(nums []int) (result [][]int) {
  backtrack(&result, nums, make([]int, 0, len(nums)), make(map[int]bool, len(nums)))
  
  return
5}
6
7func 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
  }
26}