1.1 最长子串

题目描述：给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串
输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"

思路：本题主要思路是要将删除s中某些字符后和targe匹配转化为判断是target是否为s的子串
判断是否为子串：使用双指针，如果当前字符相等，两个指针同时+1，否则只有母字符串的指针+1，最后判断目标字符传的指针是否等于其长度即可。
参考原文

示例代码：

func is_substr(s, target string) bool {
    j := 0
    for i := 0; i < len(s) && j < len(target); i++ {
        if s[i] == target[j] {
            j++
        }
    }
    return j == len(target)
}

func findLongestWord(s string, dictionary []string) string {
    var longest string
    for _, cur := range dictionary {
        // 如果当前字符串是s的子串，当当前字符串长度大于目前结果 或 长度相等但是当前串字典序排在前面时更新目前结果
        if is_substr(s, cur) && (len(cur) > len(longest) || len(cur) == len(longest) && cur < longest) {
            longest = cur
        }
    }
    return longest
}

1.2 两数之和

LeetCode No.167

题目描述：给定一个已按照升序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]

思路：因为输入数组有序，那么可以用左右两个指针，初始位于两端，判断当前两数和如果大于target，那么right指针减一，如果小于target，left加一，如果等于就返回。

示例代码:

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

1.3 判断链表是否存在环

LeetCode No.141

题目描述：给定一个链表，判断链表中是否有环。

思路：经典解法使用快慢指针，如果存在环两个指针一定会相遇，注意指针空的判断，避免出现野指针。

示例代码：

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    faster, slower := head.Next.Next, head.Next
    for faster != nil && faster.Next != nil && slower != nil {
        if faster == slower {
            return true
        }
        faster = faster.Next.Next
        slower = slower.Next
    }
    return false
}

1.4 接雨水

LeetCode No.42

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路：当前柱子能接的雨水数为其左右最高的柱子的较小值减当前柱子的高度

方法1：先求出每个柱子i左边的最大高度left_max[i]，右边最大高度right_max[i]，然后遍历一次计算。时间复杂度T = O(3n)

示例代码：

func trap(height []int) int {
    res, n := 0, len(height)
    if n == 0 {
        return res
    }
    left_max, right_max := make([]int, n), make([]int, n)
    left_max[0], right_max[n - 1] = height[0], height[n - 1]
    for i := 1; i < n; i++ {
        left_max[i] = max(left_max[i - 1], height[i])
    }
    for i := n - 2; i >= 0; i-- {
        right_max[i] = max(right_max[i + 1], height[i])
    }
    for i := 0; i < n; i++ {
        res += min(right_max[i], left_max[i]) - height[i]
    }
    return res
}

方法2：只需遍历一次的双指针解法，两个指针最终在最高点相遇。

示例代码：

func trap(height []int) int {
    res, left, right := 0, 0, len(height) - 1
    if right < 0 {
        return res
    }
    left_max, right_max := 0, 0
    for left < right {
        if height[left] > height[right] {
            right_max = max(right_max, height[right])
            res += right_max - height[right]
            right--
        } else {
            left_max = max(left_max, height[left])
            res += left_max - height[left]
            left++
        }
    }
    return res
}