双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。双指针可以从不同的方向向中间逼近也可以朝着同一个方向遍历。
在LeedCode中有很多题目可以通过双指针的思想来解答。其中包括：
1、有序数组的 Two Sum
Leetcode ：167. Two Sum II - Input array is sorted (Easy)
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
题目描述：在有序数组中找出两个数，使它们的和为 target。
/*使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。
指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
如果两个指针指向元素的和 sum == target，那么得到要求的结果；
如果 sum > target，移动较大的元素，使 sum 变小一些；
如果 sum < target，移动较小的元素，使 sum 变大一些。*/
func twoSum(numbers []int, target int) []int {
for i,j :=0,len(numbers)-1;i<j;{
if numbers[i] + numbers[j] == target {
return []int{i+1,j+1}
}
if numbers[i] + numbers[j] < target {
i++
continue
}
if numbers[i] + numbers[j] > target {
j--
continue
}
}
return []int{}
}
2、两数平方和
633. Sum of Square Numbers (Easy)
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
题目描述：判断一个数是否为两个数的平方和。
/*设置两个指针，一个从前（0）开始遍历，一个从后（sqrt(n)）开始遍历，直到找到合适的解
*/
func judgeSquareSum(c int) bool {
for i,j:=0,int(math.Sqrt(float64(c)));i<=j;{
if i*i + j*j == c {
return true
}
if i*i + j*j < c {
i++
continue
}
if i*i + j*j > c {
j--
continue
}
}
return false
}
3、反转字符串中的元音字符
345. Reverse Vowels of a String (Easy)
Given s = "leetcode", return "leotcede".
/*使用双指针指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历，发现两个元音后交换*/
func reverseVowels(s string) string {
bs := []byte(s)
for i,j:=0,len(bs)-1;i<j;{
if !isVowel(bs[i]){
i++
continue
}
if !isVowel(bs[j]){
j--
continue
}
temp:=bs[i]
bs[i]=bs[j]
bs[j]=temp
i++
j--
}
return string(bs)
}
func isVowel(b byte) bool {
return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' || b == 'A' || b == 'E' || b == 'I' || b == 'O' || b == 'U'
}
4、回文字符串
680. Valid Palindrome II (Easy)
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
题目描述：可以删除一个字符，判断是否能构成回文字符串。
/*两个指针，一个从前一个往后，一致继续往前，不一致则分别看过滤哪一边可以继续*/
func validPalindrome(s string) bool {
bs := []byte(s)
for i,j:=0,len(bs)-1;i<j;{
if bs[i] != bs[j] { //发现不一致，分别看去掉左边还是去掉右边任意一个可以就通过
return ispalindrome(bs,i+1,j) || ispalindrome(bs,i,j-1)
}
i++
j--
}
return true
}
func ispalindrome(bs []byte, left,right int) bool {
for ;left < right;{
if bs[left] != bs[right]{
return false
}
left++
right--
}
return true
}
5、归并两个有序数组
88. Merge Sorted Array (Easy)
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
题目描述：把归并结果存到第一个数组上。
/*从尾开始遍历,逐个比较添加到nums1上*/
func merge(nums1 []int, m int, nums2 []int, n int) {
index := m+n-1
for index1,index2 := m-1,n-1;index1 >=0 || index2 >=0;index--{
if index1< 0 {
nums1[index] = nums2[index2]
index2--
}else if index2 < 0 {
nums1[index] = nums1[index1]
index1--
}else if nums1[index1] <= nums2[index2] {
nums1[index] = nums2[index2]
index2--
}else if nums1[index1] > nums2[index2]{
nums1[index] = nums1[index1]
index1--
}
}
}
6、判断链表是否存在环
141. Linked List Cycle (Easy)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/*使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == NULL || head->next==NULL){
return false;
}
ListNode* l1 = head;
ListNode* l2 = head->next;
while(l2!=NULL && l2->next!=NULL){
if (l1==l2){
return true;
}else{
l1=l1->next;
l2=l2->next->next;
}
}
return false;
}
};
7、最长子序列
524. Longest Word in Dictionary through Deleting (Medium)
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"
题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最大字符串。
/*两个指针从头开始查看是否能吻合，如果查到d中字串的最后一个字符也吻合代表能够完全match，再处理同长度的问题*/
func findLongestWord(s string, d []string) string {
result := ""
for _,v := range d {
if len(result) > len(v) || len(result) == len(v) && result <= v {
continue
}
if isValid(s,v) {
result = v
}
}
return result
}
func isValid(s string,v string) bool{ //看是不是能match上
bs := []byte(s)
bv := []byte(v)
i,j:= 0,0
for i< len(bs) && j<len(bv){
if bs[i] == bv[j]{
j++
}
i++
}
if j== len(bv) { //最后一个也符合。
return true
}
return false
}
