Week 42 @ 2024 算法周记【双指针数组】

By Bryan
3 min

LC 26. Remove Duplicates from Sorted Array 删除有序数组中的重复项

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

func removeDuplicates(nums []int) int { i := 0 j := 1 for ; j < len(nums); j++ { if nums[j] == nums[j-1] { // duplicate continue } nums[i+1] = nums[j] i++ } return i+1 }

另一种解法：思路类似，只是代码组织形式不同

func removeDuplicates(nums []int) int { slow, fast := 0, 0 for fast < len(nums) { if nums[fast] != nums[slow] { slow++ nums[slow] = nums[fast] } fast++ } return slow+1 }

LC 83. Remove Duplicates from Sorted List 删除排序链表中的重复元素

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func deleteDuplicates(head *ListNode) *ListNode { if head == nil { return nil } slow, fast := head, head for fast != nil { if slow.Val != fast.Val { slow.Next = fast slow = slow.Next } fast = fast.Next } slow.Next = nil return head }

注意：数组版本保证至少有一个元素，而链表版本并没有保证，所以链表版本的代码需要判断是否为空（否则会空指针异常）

LC 27. Remove Element 移除元素

https://leetcode.com/problems/remove-element/

func removeElement(nums []int, val int) int { slow, fast := 0, 0 for ; fast < len(nums); fast++ { if nums[fast] != val { nums[slow] = nums[fast] slow++ } } return slow }

LC 283. Move Zeroes 移动零

https://leetcode.com/problems/move-zeroes/

func moveZeroes(nums []int) { slow, fast := 0, 0 for ; fast < len(nums); fast++ { if nums[fast] != 0 { nums[slow] = nums[fast] slow++ } } for i := slow; i < len(nums); i++ { nums[i] = 0 } }

其实和上面的「移除元素」一样，只不过不是返回 slow 而是把 nums[slow..] 赋值为 0

func moveZeroes(nums []int) { x := removeElement(nums, 0) for i := x; i < len(nums); i++ { nums[i] = 0 } } func removeElement(nums []int, val int) int { slow, fast := 0, 0 for ; fast < len(nums); fast++ { if nums[fast] != val { nums[slow] = nums[fast] slow++ } } return slow }

LC 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

func twoSum(nums []int, target int) []int { i, j := 0, len(nums) - 1 for i < j { if nums[i] + nums[j] == target { return []int{i + 1, j + 1} } else if nums[i] + nums[j] < target { i++ } else { j-- } } return nil // impossible }

注意返回的 index 是 1-based

LC 344. Reverse String 反转字符串

https://leetcode.com/problems/reverse-string/

func reverseString(s []byte) { i, j := 0, len(s)-1 for i < j { s[i], s[j] = s[j], s[i] i++ j-- } }

LC 5. Longest Palindromic Substring 最长回文子串

https://leetcode.com/problems/longest-palindromic-substring/

func longestPalindrome(s string) string { result := "" for i := 0; i < len(s); i++ { ps := longestPalindrome1(s, i) if len(ps) > len(result) { result = ps } } for i := 0; i < len(s)-1; i++ { ps := longestPalindrome2(s, i, i+1) if len(ps) > len(result) { result = ps } } return result } func longestPalindrome1(s string, center int) string { i, j := center, center for i >= 0 && j < len(s) && s[i] == s[j] { i-- j++ } return s[i+1:j] } func longestPalindrome2(s string, centerL, centerR int) string { i, j := centerL, centerR for i >= 0 && j < len(s) && s[i] == s[j] { i-- j++ } return s[i+1:j] }

精简、合并一些代码

func longestPalindrome(s string) string { result := "" for i := 0; i < len(s); i++ { ps := palindrome(s, i, i) if len(ps) > len(result) { result = ps } ps = palindrome(s, i, i+1) if len(ps) > len(result) { result = ps } } return result } // 在 s 中寻找以 s[centerL] 和 s[centerR] 为中心的最长回文串 func palindrome(s string, centerL, centerR int) string { i, j := centerL, centerR for i >= 0 && j < len(s) && s[i] == s[j] { i-- j++ } return s[i+1:j] }

进阶解法：Manacher 算法

Related content