算法思想
双指针是一种思想，一种技巧或一种方法，并不是什么特别具体的算法。
具体通过使用两个变量指向数组的不同位置，方便进行一些操作，如快慢指针丶左右指针，滑动窗口算法。
167.两数之和 II - 输入有序数组
题目
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 说明: 返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例: 输入: nums = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 数组nums为有序数组, 可以使用左右指针，一个初始指向最小值(左指针)，一个初始指向最大值(右指针)，
左指针往右移动，右指针往左移动。 - 设左指针变量为i, 右指针变量为j, 目标值为target。
- 如果nums[i] + nums[j] == target则得到所求解。
- 如果nums[i] + nums[j] > target，那么移动右指针。
- 如果nums[i] + nums[j] < target，那么移动左指针。
- 不满足以上三种情况则找不到结果。
代码示例:
Go
func twoSum(numbers []int, target int) []int {
res := make([]int, 2)
i, j := 0, len(numbers) - 1
for i < j {
if numbers[i] + numbers[j] == target {
res[0], res[1] = i + 1, j + 1 // 注意题目中索引是从１开始的
return res
}else if numbers[i] + numbers[j] < target {
i++
}else {
j--
}
}
return res
}633. 平方数之和
题目
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。 示例1: 输入: 5 输出: True 解释: 1 * 1 + 2 * 2 = 5 示例2: 输入: 3 输出: False 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sum-of-square-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 两数之和与两数字平方和类似，可以使用双指针遍历。
- 设左指针变量为i, 右指针变量为j。i初始为0, 使遍历次数最少，j 应该为 target的开平方。
- 左右指针的平方和为: powSum = i * i + j * j。
- 如果 powSum < target则左指针右移。
- 如果 powSum > target则右指针左移。
- 如果 powSum = target 则返回True。
- 其他返回Flase。
代码
Go
func judgeSquareSum(c int) bool {
if c < 0 {
return false
}
i, j := 0, int(math.Sqrt(float64(c)))
for i <= j {
powSum := i * i + j * j
if powSum == c {
return true
}else if powSum < c {
i ++
}else {
j--
}
}
return false
}345.反转字符串中的元音字母
题目
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。 示例 1: 输入: "hello" 输出: "holle" 示例 2: 输入: "leetcode" 输出: "leotcede" 说明: 元音字母不包含字母"y"。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 使用双指针, 一个从左往右遍历，一个从右往左遍历，当两个指针都遇到元音字母，则交换这两个元音字母。
- 将元音字母都存储起来，方便判断是否字母是否为元音字母。
代码
Go
func reverseVowels(s string) string {
r := []rune(s) // 字符串不可修改，转为rune类型
// 存储所有的元音字母
vowelLetter := map[rune]int{'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1, 'A': 1, 'E': 1, 'I': 1, 'O': 1, 'U':1}
i, j := 0, len(s) - 1
for i <= j {
if vowelLetter[r[i]] != 1{ // 如果左指针指向的非元音字符， 则右移
i++
}else if vowelLetter[r[j]] != 1 { // 如果右指针指向的为非元音字符，则左移
j--
}else { // 元音字母进行交换
r[i], r[j] = r[j], r[i]
i++
j--
}
}
return string(r)
}680.验证回文字符串 Ⅱ
题目
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解释: 你可以删除c字符。 注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-palindrome-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 可以使用左右指针遍历, 当左右指针分别指向的字符不相同时，删除一个字符再进行判断是否为回文串。
- 删除元素后判断回文串不需要判断整个字符串，之前的字符已经使用左右指针进行判断了，所以只要判断剩余的字符串是否回回文串即可。
- 删除字符串可以选择删除左指针指向的字符，也可以删除右指针指向的字符。
代码
package main
import "fmt"
func validPalindrome(s string) bool {
i, j := 0, len(s) - 1
for i < j {
if s[i] != s[j] {
return isPalindrome(s, i, j - 1) || isPalindrome(s, i+1, j)
}
i++
j--
}
return true
}
/**
左右指针遍历判断是否为回文串
*/
func isPalindrome(s string, i, j int) bool {
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
func main() {
fmt.Println(validPalindrome("abscca"))
fmt.Println(validPalindrome("abca"))
}88.合并两个有序数组
题目
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例: 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 设两指针分别指向nums1和nums2，对分别指向的值进行判断。
- 题目要求将数组合并到nums1中，所以要从数组末尾开始遍历，否则会将nums1的数据覆盖掉。
代码
Go
/**
- 设两指针分别指向nums1和nums2，对分别指向的值进行判断。
- 题目要求将数组合并到nums1中，所以要从数组末尾开始遍历，否则会将nums1的数据覆盖掉。
*/
func merge(nums1 []int, m int, nums2 []int, n int) {
p := m + n -1
m, n = m - 1, n - 1 // m, n 是数组长度, 减一当索引用
for m>=0 || n>=0{
if m < 0 { // nums1已经合并完了, 剩余的都是nums2数据
nums1[p] = nums2[n]
n--
} else if n < 0 { // nums2已经合并完了, 剩余的都是nums1数组
nums1[p] = nums1[m]
m--
} else if nums1[m] > nums2[n] { // 大的数先合并
nums1[p] = nums1[m]
m--
} else {
nums1[p] = nums2[n]
n--
}
p-- // 移至下一次需合并的位置
}
}141.环形链表
题目
给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
设两个指针，一个一次移动一个结点，一个一次移动两个结点，如果链表有环，那么这两个指针一定会相遇。
代码
Go
/**
判断链表是否有环
*/
func hasCycle(head *ListNode) bool {
if head == nil {
return false
}
l1, l2 := head, head.Next
for l1 != nil && l2!=nil && l2.Next !=nil {
if l1 == l2 { // 节点相遇, 说明有环
return true
}
l1 = l1.Next // 移至下一个节点
l2 = l2.Next.Next // 移至下两个节点
}
return false
}524.通过删除字母匹配到字典里最长单词
题目
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。 示例 1: 输入: s = "abpcplea", d = ["ale","apple","monkey","plea"] 输出: "apple" 示例 2: 输入: s = "abpcplea", d = ["a","b","c"] 输出: "a" 说明: 所有输入的字符串只包含小写字母。 字典的大小不会超过 1000。 所有输入的字符串长度不会超过 1000。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 题目中该字符串s可以通过删除给定字符串的某些字符来得到t, 则t为s的子序列。
- 可以通过双指针来判断字符串t是否为字符串s的子序列, 遍历时候比较两个字符是否相等，且记录相等字符数量sum, 如果sum等于字符t的长度，那么该字符串t则为s的子序列。
- 题目中还需要按字符串的字典序排序输出。
代码
func findLongestWord(s string, d []string) string {
var longestWord string
for _, target := range d {
l1, l2 := len(longestWord), len(target)
// 保存的最长序列和当前序列的长度， 以及判断字典序大小
if l1 > l2 || (l1 == l2 && strings.Compare(longestWord, target) == -1){
continue
}
// 如果是子序列则更新
if isSubstr(s, target) {
longestWord = target
}
}
return longestWord
}
/**
使用双指针判断某字符串是否为另一字符串的子序列
*/
func isSubstr(s string, target string) bool {
i, j := 0, 0
for i < len(s) && j < len(target) {
if s[i] == target[j] {
j++
}
i++
}
return j == len(target)
}代码已上传至Github。
京公网安备 11010502036488号