算法笔试-双指针

Updated Time	2024-11-04
Category	算法
Tags

关于语言：一刷用 Golang，二刷用 Rust

题单来源于：分享丨【题单】滑动窗口与双指针（定长/不定长/至多/至少/恰好/单序列/双序列/三指针）

双指针

相向双指针

两个指针 \(left = 0, right = n - 1\)，从数组的两端开始，向中间移动。

题目	来源	难度	分数
344. 反转字符串		简单
1750. 删除字符串两端相同字符后的最短长度	第 45 场双周赛 Q3	中等	1502
2105. 给植物浇水 II	第 271 场周赛 Q3	中等	1507
977. 有序数组的平方	第 120 场周赛	简单	1130
658. 找到 K 个最接近的元素		中等
1471. 数组中的 k 个最强值	第 192 场周赛 Q2	中等	1332
167. 两数之和 II - 输入有序数组		中等
633. 平方数之和		中等
2824. 统计和小于目标的下标对数目	第 111 场双周赛 Q1	简单	1166
15. 三数之和		中等
1577. 数的平方等于两数乘积的方法数	第 205 场周赛	中等	1594
11. 盛最多水的容器		中等
42. 接雨水		中等
1616. 分割两个字符串得到回文串	第 210 场周赛 Q3	中等	1868

原地修改

题目	来源	难度	分数
27. 移除元素		简单
26. 删除有序数组中的重复项		简单
283. 移动零		简单
905. 按奇偶排序数组	第 102 场周赛 Q1	简单	1178
922. 按奇偶排序数组 II	第 106 场周赛 Q1	简单	1174
2460. 对数组执行操作	第 318 场周赛 Q1	简单	1224
1089. 复写零	第 141 场周赛 Q1	简单	1263

双序列双指针

题目	来源	难度	分数
2540. 最小公共值	第 96 场双周赛 Q1	简单	1250
88. 合并两个有序数组		简单
2570. 合并两个二维数组 - 求和法	第 333 场周赛 Q1	简单	1281
LCP 18. 早餐组合		简单
1855. 下标对中的最大距离	第 240 场周赛 Q2	中等	1515
925. 长按键入	第 107 场周赛 Q1	简单	1271

判断子序列

题目	来源	难度	分数
392. 判断子序列		简单
524. 通过删除字母匹配到字典里最长单词		中等
2486. 追加字符以获得子序列	第 321 场周赛 Q2	中等	1363
2825. 循环增长使字符串子序列等于另一个字符串	第 111 场双周赛 Q2	中等	1415
1023. 驼峰式匹配	第 131 场周赛 Q3	中等	1537
3132. 找出与数组相加的整数 II	第 395 场周赛 Q2	中等	1620
522. 最长特殊序列 II		中等

题解

344. 反转字符串

func reverseString(s []byte)  {
    for l, r := 0, len(s) - 1; l < r; l, r = l + 1, r - 1 {
        s[l], s[r] = s[r], s[l]
    }
    return
}

1750. 删除字符串两端相同字符后的最短长度

func minimumLength(s string) int {
    n := len(s)
    left, right := 0, n - 1
    for left < right && s[left] == s[right] {
        c := s[left]
        for left <= right && s[left] == c {
            left++
        }
        for left <= right && s[right] == c {
            right--
        }
    }
    return right - left + 1
}

2105. 给植物浇水 II

func minimumRefill(plants []int, capacityA int, capacityB int) (ans int) {
    left, right := 0, len(plants) - 1
    A, B := capacityA, capacityB
    for left < right {
        if A < plants[left] {
            ans++
            A = capacityA
        }
        A -= plants[left]
        left++
        if B < plants[right] {
            ans++
            B = capacityB
        }
        B -= plants[right]
        right--
    }
    if left == right && max(A, B) < plants[left] {
        ans++
    }
    return
}

977. 有序数组的平方

func sortedSquares(nums []int) []int {
    ans := make([]int, len(nums))
    p, left, right := len(nums) - 1, 0, len(nums) - 1
    for left <= right {
        a, b := nums[left], nums[right]
        if abs(a) < abs(b) {
            ans[p] = b * b
            right--
        } else {
            ans[p] = a * a
            left++
        }
        p--
    }
    return ans
}

func abs(v int) int {
    if v < 0 { return -v }
    return v
}

658. 找到 K 个最接近的元素

func findClosestElements(arr []int, k int, x int) []int {
    left, right := 0, len(arr) - 1
    for right - left + 1 > k {
        a, b := arr[left], arr[right]
        if abs(a - x) <= abs(b - x) {
            right--
        } else {
            left++
        }
    }
    return arr[left:right+1]
}

func abs(v int) int {
    if v < 0 { return -v }
    return v
}

1471. 数组中的 k 个最强值

func getStrongest(arr []int, k int) []int {
    sort.Ints(arr)
    n := len(arr)
    m := arr[(n-1)/2]
    left, right, p := 0, n - 1, 0
    ans := make([]int, k)
    for right - left + 1 > n - k {
        a, b := arr[left], arr[right]
        if abs(a - m) > abs(b - m) {
            left++
            ans[p] = a
        } else {
            right--
            ans[p] = b
        }
        p++
    }
    return ans
}

func abs(v int) int {
    if v < 0 { return -v }
    return v
}

167. 两数之和 II - 输入有序数组

func twoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers) - 1
    for left < right {
        remain := target - numbers[left]
        if numbers[right] == remain {
            return []int{left + 1, right + 1}
        } else if numbers[right] > remain {
            right--
        } else {
            left++
        }
    }
    return []int{-1, -1}
}

633. 平方数之和

func judgeSquareSum(c int) bool {
    l, r := 0, int(math.Sqrt(float64(c)))
    for l <= r {
        s := l * l + r * r
        if s == c {
            return true
        }
        if s < c {
            l++
        } else {
            r--
        }
    }
    return false
}

2824. 统计和小于目标的下标对数目

func countPairs(nums []int, target int) (ans int) {
    sort.Ints(nums)
    l, r := 0, len(nums) - 1
    for l < r {
        s := nums[l] + nums[r]
        if s < target {
            ans += r - l
            l++
        } else {
            r--
        }
    }
    return
}

15. 三数之和

func threeSum(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
    for i, num := range nums {
        if i > 0 && num == nums[i-1] {
            continue
        }
        j, k := i + 1, n - 1
        for j < k {
            s := num + nums[j] + nums[k]
            if s > 0 {
                k--
            } else if s < 0 {
                j++
            } else {
                ans = append(ans, []int{num, nums[j], nums[k]})
                j++
                k--
                for j < k && nums[j] == nums[j-1] { j++ }
                for j < k && nums[k] == nums[k+1] { k-- }
            }
        }
    }
    return
}

1577. 数的平方等于两数乘积的方法数

func numTriplets(nums1 []int, nums2 []int) int {
    sort.Ints(nums1)
    sort.Ints(nums2)

    var f func(a []int, b []int) int

    f = func (a []int, b []int) int {
        ans := 0
        for _, i := range a {
            l, r, x := 0, len(b) - 1, int64(i * i)
            for l < r {
                s := int64(b[l] * b[r])
                if s < x {
                    l++
                } else if s > x {
                    r--
                } else {
                    if b[l] == b[r] {
                        ans += (r - l + 1) * (r - l) / 2
                        break
                    } else {
                        cnt1, cnt2 := 0, 0
                        j, k := b[l], b[r]
                        for j == b[l] { cnt1++; l++ }
                        for k == b[r] { cnt2++; r-- }
                        ans += cnt1 * cnt2
                    }
                }
            }
        }
        return ans
    }

    return f(nums1, nums2) + f(nums2, nums1)
}

11. 盛最多水的容器

func maxArea(height []int) (ans int) {
    l, r := 0, len(height) - 1
    for l < r {
        ans = max(ans, (r - l) * min(height[l], height[r]))
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return
}

42. 接雨水

func trap(height []int) (ans int) {
    l, r := 0, len(height) - 1
    preMax, sufMax := 0, 0
    for l <= r {
        preMax = max(preMax, height[l])
        sufMax = max(sufMax, height[r])
        if preMax < sufMax {
            ans += preMax - height[l]
            l++
        } else {
            ans += sufMax - height[r]
            r--
        }
    }
    return
}

1616. 分割两个字符串得到回文串

func checkPalindromeFormation(a string, b string) bool {
    var check func(s string, i, j int) bool
    var helper func(a, b string) bool

    check = func(s string, i, j int) bool {
        for i < j && s[i] == s[j] {
            i++
            j--
        }
        return i >= j
    }

    helper = func(a, b string) bool {
        i, j := 0, len(a) - 1
        for i < j && a[i] == b[j] {
            i++
            j--
        }
        return check(a, i, j) || check(b, i, j)
    }
    return helper(a, b) || helper(b, a)
}

27. 移除元素

func removeElement(nums []int, val int) int {
    sort.Ints(nums)
    left, right := 0, len(nums) - 1
    for left <= right {
        if nums[left] == val {
            nums[left] = nums[right]
            right--
        } else {
            left++
        }
    }
    return left
}

26. 删除有序数组中的重复项

func removeDuplicates(nums []int) int {
    l := 0
    for r, num := range nums {
        if r != 0 && num != nums[r-1] {
            l++
            nums[l] = num
        }
    }
    return l + 1
}

283. 移动零

func moveZeroes(nums []int)  {
    l := 0
    for r, num := range nums {
        if num != 0 {
            nums[r], nums[l] = nums[l], num
            l++
        }
    }
}

905. 按奇偶排序数组

func sortArrayByParity(nums []int) []int {
    l := 0
    for r, num := range nums {
        if num & 1 == 0 {
            nums[r], nums[l] = nums[l], num
            l++
        }
    }
    return nums
}

922. 按奇偶排序数组 II

func sortArrayByParityII(nums []int) []int {
    l, r := 0, 1
    for l < len(nums) {
        if nums[l] & 1 == 1 {
            nums[r], nums[l] = nums[l], nums[r]
            r += 2
        } else {
            l += 2
        }
    }
    return nums
}

2460. 对数组执行操作

func applyOperations(nums []int) []int {
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i-1] {
            nums[i-1], nums[i] = nums[i-1] * 2, 0
        }
    }
    l := 0
    // 283. 移动零
    for r, num := range nums {
        if num != 0 {
            nums[r], nums[l] = nums[l], nums[r]
            l++
        }
    }
    return nums
}

1089. 复写零

func duplicateZeros(arr []int)  {
    l, r, k := 0, len(arr) - 1, len(arr) - 1
    for l < r {
        if arr[l] == 0 {
            r--
        }
        l++
    }
    if l == r && arr[l] == 0 {
        arr[k] = arr[r]
        k--
        r--
    }
    for r >= 0 {
        if arr[r] == 0 {
            arr[k] = 0
            k--
        }
        arr[k] = arr[r]
        k--
        r--
    }
}

2540. 最小公共值

func getCommon(nums1 []int, nums2 []int) int {
    i, j := 0, 0
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] == nums2[j] {
            return nums1[i]
        }
        if nums1[i] > nums2[j] {
            j++
        } else {
            i++
        }
    }

    return -1
}

88. 合并两个有序数组

func merge(nums1 []int, m int, nums2 []int, n int)  {
    p := m + n - 1
    i, j := m - 1, n - 1
    for i >= 0 && j >= 0 {
        if nums1[i] > nums2[j] {
            nums1[p] = nums1[i]
            i--
        } else {
            nums1[p] = nums2[j]
            j--
        }
        p--
    }
    fmt.Println(i, j, p)
    for i >= 0 {
        nums1[p] = nums1[i]
        i--
        p--
    }
    for j >= 0 {
        nums1[p] = nums2[j]
        j--
        p--
    }
}

2570. 合并两个二维数组 - 求和法

func mergeArrays(nums1 [][]int, nums2 [][]int) [][]int {
    n, m := len(nums1), len(nums2)
    ans := make([][]int, 0)
    i, j := 0, 0
    for i < n && j < m {
        a, b := nums1[i], nums2[j]
        if a[0] == b[0] {
            ans = append(ans, []int{a[0], a[1] + b[1]})
            i, j = i + 1, j + 1
        } else if a[0] > b[0] {
            ans = append(ans, []int{b[0], b[1]})
            j++
        } else {
            ans = append(ans, []int{a[0], a[1]})
            i++
        }
    }
    for i < n {
        a := nums1[i]
        ans = append(ans, []int{a[0], a[1]})
        i++
    }
    for j < m {
        b := nums2[j]
        ans = append(ans, []int{b[0], b[1]})
        j++
    }
    return ans
}

LCP 18. 早餐组合

对两个序列排序，每个序列上放一个指针，指针 \(j\) 从大到小遍历，指针 \(i\) 从小到大遍历。每次固定 \(j\)，移动 \(i\)，只要 \(sum \le x\) 那么比 \(j\) 小的所有位置都可以。当 \(sum > x\) 就需要让 \(j - 1\)，直到 \(sum\) 再次比 \(x\) 小为止。

const MOD int64 = 1000000007
func breakfastNumber(staple []int, drinks []int, x int) int {
    sort.Ints(staple)
    sort.Ints(drinks)
    i, j := 0, len(drinks) - 1
    ans := int64(0)
    for i < len(staple) && j >= 0 {
        sum := staple[i] + drinks[j]
        if sum <= x {
            i++
            ans += int64(j + 1)
            ans %= MOD
        } else {
            j--
        }
    }
    return int(ans % MOD)
}

1855. 下标对中的最大距离

func maxDistance(nums1 []int, nums2 []int) (ans int) {
    i, j := 0, 0
    n, m := len(nums1), len(nums2)
    for i < n && j < m {
        if nums1[i] > nums2[j] {
            if i == j { j++ }
            i++
        } else {
            ans = max(ans, j - i)
            j++
        }
    }
    return
}

925. 长按键入

func isLongPressedName(name string, typed string) bool {
    i, j := 0, 0
    n, m := len(name), len(typed)
    for j < m {
        if i < n && name[i] == typed[j] {
            i, j = i + 1, j + 1
        } else if j > 0 && typed[j] == typed[j-1] {
            j++
        } else {
            return false
        }
    }
    return i == n
}

392. 判断子序列

func isSubsequence(s string, t string) bool {
    i, j := 0, 0
    n, m := len(s), len(t)
    for i < n && j < m {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == n
}

524. 通过删除字母匹配到字典里最长单词

func findLongestWord(s string, dictionary []string) string {
    sort.Slice(dictionary, func(i, j int) bool {
		if len(dictionary[i]) != len(dictionary[j]) {
			return len(dictionary[i]) > len(dictionary[j])
		}
		return dictionary[i] < dictionary[j]
	})
    for _, w := range dictionary {
        i, j := 0, 0
        for i < len(w) && j < len(s) {
            if w[i] == s[j] {
                i++
            }
            j++
        }
        if i == len(w) {
            return w
        }
    }
    return ""
}

2486. 追加字符以获得子序列

func appendCharacters(s string, t string) int { 
    i, j := 0, 0
    n, m := len(s), len(t)
    for i < n {
        if j < m && s[i] == t[j] {
            j++
        }
        i++
    }
    return m - j
}

2825. 循环增长使字符串子序列等于另一个字符串

func canMakeSubsequence(str1 string, str2 string) bool {
    i, j := 0, 0
    n, m := len(str1), len(str2)
    for i < n {
        a, b := str1[i], str1[i] + 1
        if a == 'z' {
            b = 'a'
        }
        if j < m && (a == str2[j] || b == str2[j]) {
            j++
        }
        i++
    }
    return j == m
}

3132. 找出与数组相加的整数 II

只能移除两个元素，所以 \(nums_1\) 前三小元素必定有一个是保留下来的，可以枚举保留下来的最小元素是 \(nums_1[0]\) 还是 \(nums_1[1]\) 还是 \(nums_1[2]\)

func minimumAddedInteger(nums1 []int, nums2 []int) int {
    sort.Ints(nums1)
    sort.Ints(nums2)
    for i := 2; i > 0; i-- {
        x := nums2[0] - nums1[i]
        j := 0
        for _, v := range nums1[i:] {
            if nums2[j] == v + x {
                j++
                if j == len(nums2) {
                    return x
                }
            }
        }
    }
    return nums2[0] - nums1[0]
}

1023. 驼峰式匹配

func camelMatch(queries []string, pattern string) []bool {
    ans := make([]bool, len(queries))
    for k, query := range queries {
        i, j := 0, 0
        n, m := len(query), len(pattern)
        ans[k] = true
        for i < n {
            if j < m && query[i] == pattern[j] {
                j++
            } else if query[i] >= 'A' && query[i] <= 'Z' {
                ans[k] = false
                break
            }
            i++
        }
        if j != m {
            ans[k] = false
        }
    }
    return ans
}

522. 最长特殊序列 II

func findLUSlength(strs []string) int {
    check := func(a, b string) bool {
        j := 0
        for i := 0; j < len(a) && i < len(b); i++ {
            if a[j] == b[i] {
                j++
            }
        }
        return j == len(a)
    }

    ans := -1
    for i, a := range strs {
        x := len(a)
        for j, b := range strs {
            if i != j && check(a, b) {
                x = -1
                break
            }
        }
        ans = max(ans, x)
    }
    return ans
}

1. 双指针