【算法】双指针

双指针

移除元素

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

func removeElement(nums []int, val int) int {
    var end int = len(nums) - 1
    var start int = 0

    for start <= end {
        for nums[start] == val && start <= end {
            nums[start] = nums[end]
            end--
        }
        start ++
    }

    return end + 1
}

剑指Offer 05.替换空格

https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

func replaceSpace(s string) string {
    s2byte := make([]byte, len(s))
    emptycnt := 0
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            emptycnt ++
        }
    }

    for emptycnt > 0 {
        emptycnt --
        s2byte = append(s2byte, ' ', ' ')
    }

    for i, j := len(s)-1, len(s2byte)-1; i >= 0; {
        if s[i] == ' ' {
            s2byte[j] = '0'
            s2byte[j-1] = '2'
            s2byte[j-2] = '%'
            j -= 3
        } else {
            s2byte[j] = s[i]
            j --
        }
        i --
    }
    res := string(s2byte)
    return res
}

移除元素

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

/*
因为不要求元素按照之前的排列，所以可以使用双指针，一个指针从前往后用来扫描数组，另一个指针从后往前将后面的元素添加到删除元素后的空位
*/
func removeElement(nums []int, val int) int {
    var end int = len(nums) - 1
    var start int = 0

    for start <= end {
        for nums[start] == val && start <= end {
            nums[start] = nums[end]
            end--
        }
        start ++
    }

    return end + 1
}

三数之和

https://leetcode-cn.com/problems/3sum/

方式是先对数组进行排序，然后通过双重循环，外层i遍历整个数组，内层通过双指针left=i+1, right=len-1
如果三数之和大于0，则left++
如果三数之和小于0，则right--
因为不能有重复的答案，i和left都需要看是不是和上一个元素相同

import (
    "sort"
)
func threeSum(nums []int) [][]int {
    res := make([][]int, 0)
    var left, right, length int
    length = len(nums)
    sort.Ints(nums)
    for i := 0; i < length; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        left = i + 1
        right = length - 1
        for left < right {
            if left > i + 1 && nums[left] == nums[left-1] {
                left ++
                continue
            }
            if nums[i] + nums[left] + nums[right] > 0 {
                right --
            } else if nums[i] + nums[left] + nums[right] < 0 {
                left ++
            } else {
                res = append(res, []int{nums[i], nums[left], nums[right]})
                left ++
            }
        }
    }
    return res
}

四数之和

https://leetcode-cn.com/problems/4sum/

和三数之和类似，只是多加了一层循环

import "sort"
func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    ans := make([][]int, 0)
    llen := len(nums)
    for i := 0; i < llen; i++ {
        if i > 0 && nums[i] == nums[i - 1] {
            continue
        }
        for j := i + 1; j < llen; j++ {
            if j > i + 1 && nums[j] == nums[j - 1] {
                continue
            }
            left := j + 1
            right := llen - 1
            for left < right {
                if left > j + 1 && nums[left] == nums[left - 1] {
                    left ++
                    continue
                }
                if nums[i] + nums[j] + nums[left] + nums[right] > target {
                    right --
                } else if nums[i] + nums[j] + nums[left] + nums[right] < target {
                    left ++
                } else {
                    ans = append(ans, []int{nums[i], nums[j], nums[left], nums[right]})
                    left ++
                }
            }
        }
    }
    return ans
}

反转字符串里的单词

https://leetcode-cn.com/problems/reverse-words-in-a-string/

首先将字符串中的多余空格去，可以使用https://leetcode-cn.com/problems/remove-element/里的思想，然后将整个字符串逆序，然后再将字符串的每个单词进行反转就可以了

// 直接使用内置函数，这种方式就是熟悉一下go中的字符串操作还可以
import "strings"

func reverse(strsplit []string) []string {
    for i, j := 0, len(strsplit)-1; i < j; i, j = i+1, j-1 {
        strsplit[i], strsplit[j] = strsplit[j], strsplit[i]
    }
    return strsplit
}

func reverseWords(s string) string {
    splitstr := reverse(strings.Fields(s))
    return strings.Join(splitstr, " ")
}


// 第二种方式就是上面说的

链表相交※

https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/

思路就是先求出两个链表的长度，求出两链表的差值，然后先让长的链表移动差值步，然后二者一块移动看指针是否相同。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    
    i, j := 0, 0

    tmp := headA
    for tmp != nil {
        tmp = tmp.Next
        i ++
    }

    tmp = headB
    for tmp != nil {
        tmp = tmp.Next
        j ++
    }

    var tmp1, tmp2 *ListNode
    var k int

    if i > j {
        tmp1 = headA
        tmp2 = headB
        k = i - j
    } else {
        tmp1 = headB
        tmp2 = headA
        k = j - i
    }

    for k > 0 {
        k-- 
        tmp1 = tmp1.Next
    }

    for tmp1 != tmp2 {
        tmp1 = tmp1.Next
        tmp2 = tmp2.Next
    }

    return tmp1

}

环形链表Ⅱ※

https://leetcode-cn.com/problems/linked-list-cycle-ii/

设置快慢指针，快指针一次走两步，慢指针一次走一步，二者相遇时一定是在环内，假设头节点到环的入口距离为$x$，入口到快慢指针相遇的位置距离为$y$，从相遇位置到环入口位置距离为$z$，如图所示。

相遇时，慢指针走过的距离为：$x+y$

快指针走过的距离为$x+y+n(z+y)$

而快指针走过的节点是慢指针的二倍，即：$2(x+y)=x+y+n(z+y)$

最终要求的是$x$，$x=(n-1)(y+z)+z$。

当$n=1$时，$x=z$，即当两指针相遇时，从相遇节点和头节点各出发一个指针，当两指针相遇时记为头口节点。

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

    for true {
        if fast.Next != nil && fast.Next.Next != nil {
            fast = fast.Next.Next
        } else {
            return nil
        }
        slow = slow.Next
        if fast == slow {
            index1, index2 := head, fast
            for index1 != index2 {
                index1 = index1.Next
                index2 = index2.Next
            }
            return index1
        }
    }
    return nil

}

删除链表的倒数第N个节点※

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

双指针首先都指向头节点，快指针先走n步，然后快慢指针再一起走，直到快指针到结尾，那么慢指针下一个元素即时要删除的元素。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    nilhead := &ListNode{
        0,
        head,
    }

    fast, slow := nilhead, nilhead
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }

    slow.Next = slow.Next.Next

    return nilhead.Next
}