滑动窗口

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

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

暴力解法（TLE）

1func containsNearbyDuplicate(nums []int, k int) bool {
2    for i, v := range nums {
3        for j := max(i-k, 0); j <= min(i+k, len(nums)-1); j++ {
4            if i != j && nums[j] == v {
5                return true
6            }
7        }
8    }
9    return false
10}

滑动窗口

1func containsNearbyDuplicate(nums []int, k int) bool {
2    left, right := 0, 0
3    window := make(map[int]bool, len(nums))
4    for right < len(nums) {
5        if window[nums[right]] {
6            return true
7        }
8        window[nums[right]] = true
9        right++
10
11        if right - left > k {
12            window[nums[left]] = false
13            left++
14        }
15    }
16
17    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 {
2    left, right := 0, 0
3    sum := 0
4    minLength := math.MaxInt
5    for right < len(nums) {
6        sum += nums[right]
7        right++
8
9        for sum >= target && left < right {
10            minLength = min(minLength, right-left)
11            sum -= nums[left]
12            left++
13        }
14    }
15
16    if minLength == math.MaxInt {
17        return 0
18    }
19    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) {
2    sort.Ints(nums)
3
4    k := 0
5    for k < len(nums) {
6        partResults := twoSum(nums[k+1:], -nums[k])
7        for _, r := range partResults {
8            results = append(results,
9                append([]int{nums[k]}, r...),
10            )
11        }
12
13        for v := nums[k]; k < len(nums) && nums[k] == v; k++ {}
14    }
15    
16    return
17}
18
19func twoSum(nums []int, target int) (results [][]int) {
20    i, j := 0, len(nums)-1
21    for i < j {
22        sum := nums[i] + nums[j]
23        if sum == target {
24            results = append(results, []int{nums[i], nums[j]})
25
26            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
27            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
28        } else if sum < target {
29            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
30        } else {
31            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
32        }
33    }
34    return 
35}

LC 18. 4Sum 四数之和

1func fourSum(nums []int, target int) (results [][]int) {
2    sort.Ints(nums)
3
4    i := 0
5    for i < len(nums) - 3 {
6        j := len(nums) - 1
7        for i + 2 < j {
8            partResults := twoSum(nums[i+1:j], target-(nums[i]+nums[j]))
9            for _, r := range partResults {
10                results = append(results,
11                    []int{nums[i], r[0], r[1], nums[j]},
12                )
13            }
14            for v := nums[j]; j > i+2 && nums[j] == v; j-- {}
15        } 
16         for v := nums[i]; i < len(nums)-3 && nums[i] == v; i++ {}
17    }
18
19    return
20}
21
22func twoSum(nums []int, target int) (results [][]int) {
23    i, j := 0, len(nums)-1
24    for i < j {
25        sum := nums[i] + nums[j]
26        if sum == target {
27            results = append(results, []int{nums[i], nums[j]})
28
29            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
30            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
31        } else if sum < target {
32            for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
33        } else {
34            for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
35        }
36    }
37    return
38}

LC 46. Permutations 全排列

​https://leetcode.com/problems/permutations

1func permute(nums []int) (result [][]int) {
2    backtrack(&result, nums, make([]int, 0, len(nums)), make(map[int]bool, len(nums)))
3    
4    return
5}
6
7func backtrack(result *[][]int, nums []int, current []int, used map[int]bool) {
8    if len(current) == len(nums) {
9        *result = append(*result, append([]int(nil), current...))
10        return
11    }
12    
13    for _, num := range nums {
14        if used[num] {
15            continue
16        }
17        
18        current = append(current, num)
19        used[num] = true
20        
21        backtrack(result, nums, current, used)
22        
23        current = current[:len(current)-1]
24        used[num] = false
25    }
26}