枚举

前缀和

就是把某下标前的元素都加起来，结果作为在这个下标下的前缀和

例如： 有数组 a[1~n], 存在 S[1~n] 满足

$S[1] = a[1]$

$S[2] = a[1] + a[2]$

$S[3] = a[1] + a[2] + a[3]$

$...$

就称 S 为 a 的前缀和

前缀和的特点：

• 构造只需要$O(n)$ 的时间复杂度
• 能在$O(1)$的时间复杂度求解数组任意区间的和

  例如，求解a[l] +...+a[r]，使用前缀和有$S[r] - S[l - 1] = a[l] + ... + a[r]$

差分

差分是前缀和的逆运算

例如： 有数组 a[1~n], 存在 b[1~n] 满足

$b[1] = a[1]$

$b[2] = a[2] - a[1]$

$b[3] = a[3] - a[2]$

$...$

差分的特点：

• 使用差分数组构造前缀和只需要$O(n)$ 的时间复杂度
• 能在$O(1)$的时间复杂度内对数组任意期间内的数进行运算

  例如，要操作(a[l] ~ a[r]) + c, 使用差分数组要$b[l] += c, b[r+1] -= c$，差分数组的前缀和即是答案

双指针

这个比较难梳理，双指针算法在很多场景中都常见，包括很多算法，最常见的场景是数组和链表（即线性的表中）

描述： 使用两个指针（抽象概念的指针），通过适当的条件移动它们达到在不同的数据间（或同一数据的不同位置）进行灵活处理的目的

尺取法

其实就是普通的双指针思想

思路就是两个指针指向头尾，在不同的条件下移动首尾指针以遍历所有可能性结果

时间复杂度：一般为$O(n)$

例如：

3. 无重复字符的最长子串

func lengthOfLongestSubstring(s string) (res int) {
    l, r := 0, -1
    var st [127]int
    for l < len(s) {
        if r + 1 < len(s) && st[s[r+1]] == 0 {
            st[s[r+1]] ++
            r ++
        } else {
            st[s[l]] --
            l ++
        }
        res = max(res, r - l + 1)
    }
    return
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

每次移动尾指针后，若重复字符增加，就左移指针直到两指针围成字符串合法，并取合法字符串的最大长度，最后得到答案

对撞指针

11. 盛最多水的容器

func maxArea(height []int) (res int) {
    l, r := 0, len(height) - 1
    h := 0
    for l < r {
        if height[l] < height[r] {
            h = height[l]
            l ++
        } else {
            h = height[r]
            r --
        }
        res = max(res, h * (r - l + 1))
    }
    return
}

func max (a, b int) int {
    if (a < b){
        return b
    }
    return a
}

初始时，首尾指针构成的底边最长，每次把矮的边向里移动，若矮边变长则能获得更大的面积，直到两指针相遇，取其中最大的面积（具体证明看题解吧）

经典类型的模板

26. 删除有序数组中的重复项

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

27. 移除元素

func removeElement(nums []int, val int) int {
    idx := 0
    for _, v := range nums {
        if v != val {nums[idx] = v;idx ++}
    }
    return idx
}

15. 三数之和

func threeSum(nums []int) [][]int {
    res := make([][]int, 0)
    if len(nums) < 3 {
        return res
    }
    sort.Ints(nums)

    for i := 0; i < len(nums); i ++ {
        if nums[i] > 0 {
            return res
        }
        if i > 0 && nums[i - 1] == nums[i] {
            continue
        }
        L := i + 1
        R := len(nums) - 1
        for L < R {
            if nums[i] + nums[L] + nums[R] == 0 {
                res = append(res, []int{nums[i], nums[L], nums[R]})
                for L < R && nums[L] == nums[L+1] {L ++}
                for L < R && nums[R] == nums[R-1] {R --}
                L ++
                R --
            } else if nums[i] + nums[L] + nums[R] < 0 {
                L ++
            } else {
                R --
            }
        }
    }
    return res
}

18. 四数之和

func fourSum(nums []int, target int) (res [][]int) {
    len := len(nums)
    if len < 4 || nums == nil {
        return
    }
    sort.Ints(nums)
    for i := 0; i < len - 3; i ++ {
        if i > 0 && nums[i-1] == nums[i] {
            continue
        }
        for  j := i + 1; j < len - 2; j ++ {
            if j > i + 1 && nums[j-1] == nums[j] {
                continue
            }
            L, R := j + 1, len - 1
            for L < R {
                if sum := nums[i] + nums[j] + nums[L] + nums[R];sum == target {
                    res = append(res, []int{nums[i], nums[j], nums[L], nums[R]})
                    for L < R && nums[L] == nums[L+1] {L ++}
                    for L < R && nums[R] == nums[R-1] {R --}
                    L ++
                    R --
                } else if sum < target {
                    L ++
                } else {
                    R --
                }
            }
        }
    }
    return
}

TIP

这些题相似的地方都是在枚举，且在适当的条件下移动指针以优化

分而治之

二分查找

二分查找(binary search) 描述：

是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

搜索范围，我个人倾向于把二分理解成：搜索是在由l 和 r围成的区间内进行的，而每次搜索得到的信息都可以帮助减小区间，从而得以优化搜索时间

时间复杂度：$O(logn)$

二分查找的本质是边界, 即查找出由满足条件的值组成集合的边界值

模板：

int bsearch_1(int l, int r)
{
    while (l < r)

    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断 mid 是否满足性质
        else l = mid + 1;
    }
    return l;
}
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1; // 注意这里，cpp 中加法优先级比右移动高可以不加括号
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

例如：

35. 搜索插入位置

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums) - 1
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] >= target {
            r = mid
        } else {l = mid + 1}
    }
    if nums[l] < target {return l + 1}
    return l
}

查找的是满足条件nums[mid] >= target的集合左边界（即大于等于 target 的第一个数），满足此条件时r应该向左移动以缩小范围，因此选择模板一

TIP

根据check()条件来选择模板，要查找左边界还是右边界（有些情况下，集合的概念会淡化，两个模板的使用就没有区别，因此需要据条件分析）

死记硬背的话，+1 为右边界，不+1 为左边界:()

当使用到第二个模板时，mid = ( l + r + 1 ) >> 1，多加一是为了防止进入死循环；若没有加一mid = ( l + r ) >> 1，当 r = l + 1 时（即查找进入尾声，只有两个元素在查找区间） mid = ( 2*l + 1 ) >> 1 = l（cpp 默认向下取整）, 这导致了，本应当满足条件 l = r 退出循环的情况变成l = mid = l != r从而无限循环；因此加一可以避免 cpp 向下取整带来的整数二分 bug

特别题目

33. 搜索旋转排序数组

func search(nums []int, target int) int {
    if len(nums) == 0 {return -1}
    l, r := 0, len(nums) - 1

    for l <= r {
        mid := (l + r) >> 1

        if nums[mid] == target {
            return mid
        } else if nums[mid] > nums[l] {
            if target >= nums[l] && target < nums[mid] {
                r = mid - 1
            } else {l = mid + 1}
        } else if nums[mid] < nums[r] {
            if target > nums[mid] && target <= nums[r] {
                l = mid + 1
            } else {
                r = mid - 1
            }
        } else {
            if l == mid {
                l ++
            } else if r == mid {
                r --
            }
        }
    }
    return -1
}

这道题和平常二分法查找的不同就在于，把一个有序递增的数组分成了，两个递增的数组，我们需要做的就是判断这个数在哪一个递增的数组中，然后再去用常规的二分法去解决