Week 12 @ 2025 算法周记【滑动窗口 + 二分搜索】
滑动窗口
LC 220. Contains Duplicate III 存在重复元素 III
Contains Duplicate III - LeetCode
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
TreeSet<Integer> window = new TreeSet<>();
int left = 0, right = 0;
while (right < nums.length) {
Integer ceiling = window.ceiling(nums[right]);
if (ceiling != null && ceiling - nums[right] <= valueDiff) {
return true;
}
Integer floor = window.floor(nums[right]);
if (floor != null && nums[right] - floor <= valueDiff) {
return true;
}
window.add(nums[right]);
right++;
if (right - left > indexDiff) {
window.remove(nums[left]);
left++;
}
}
return false;
}
}二分搜索
LC 852. 山脉数组的峰顶索引
Peak Index in a Mountain Array - LeetCode
func peakIndexInMountainArray(arr []int) int {
// 找到 a >= a+1 的最小值
L, R := 0, len(arr)-1
for L < R {
mid := L + (R - L) / 2
if arr[mid] >= arr[mid+1] {
R = mid
} else {
L = mid + 1
}
}
return L
}剑指 Offer 53 - I. 在排序数组中查找数字 I
LCR 172. 统计目标成绩的出现次数 - 力扣（LeetCode）
func countTarget(scores []int, target int) int {
l := leftBound(scores, target)
if l == len(scores) || scores[l] != target {
return 0
}
r := leftBound(scores, target+1)
return r - l
}
func leftBound(arr []int, target int) int {
L, R := 0, len(arr)
for L < R {
mid := L + (R - L) / 2
if arr[mid] >= target {
R = mid
} else {
L = mid + 1
}
}
return L
}剑指 Offer 53 - II. 0～n-1 中缺失的数字
简单判断
func takeAttendance(records []int) int {
for i, x := range records {
if i != x {
return i
}
}
return len(records)
}利用异或
func takeAttendance(records []int) int {
result := 0
for _, x := range records {
result ^= x
}
for i := 1; i <= len(records); i++ {
result ^= i
}
return result
}利用二分
func takeAttendance(records []int) int {
n := len(records)
if records[n-1] == n-1 {
return n
}
L, R := 0, n
for L < R {
mid := L + (R - L) / 2
if records[mid] != mid {
R = mid
} else {
L = mid + 1
}
}
return L
}
LC 33. 搜索旋转排序数组
Search in Rotated Sorted Array - LeetCode
func search(nums []int, target int) int {
L, R := 0, len(nums) - 1
for L <= R {
mid := L + (R - L) / 2
if nums[mid] == target {
return mid
}
if nums[mid] >= nums[L] {
// 此时 L..mid 升序
if nums[L] <= target && target <= nums[mid] {
R = mid - 1
} else {
L = mid + 1
}
} else {
// 此时 mid..R 升序
if nums[mid] <= target && target <= nums[R] {
L = mid + 1
} else {
R = mid - 1
}
}
}
return -1
}LC 81. 搜索旋转排序数组 II
Search in Rotated Sorted Array II - LeetCode
func search(nums []int, target int) bool {
L, R := 0, len(nums) - 1
for L <= R {
for L < R && nums[L] == nums[L+1] {
L++
}
for L < R && nums[R] == nums[R-1] {
R--
}
mid := L + (R - L) / 2
if nums[mid] == target {
return true
}
if nums[mid] >= nums[L] {
// 此时 L..mid 升序
if nums[L] <= target && target <= nums[mid] {
R = mid - 1
} else {
L = mid + 1
}
} else {
// 此时 mid..R 升序
if nums[mid] <= target && target <= nums[R] {
L = mid + 1
} else {
R = mid - 1
}
}
}
return false
}