选择几个经典简单的算法来进行统一讲解，因为这些算法的思想和模板不需要单开一个章节来进行分开讲解。这些算法有：双指针、位运算的经典应用、整数有序离散化以及区间合并等内容
…

双指针算法

双指针算法问题的常见类型

对于可以应用双指针算法的问题基本上有两种类型：

• 两个指针分别指向一个序列，每个序列只有一个指针，以维护某种次序。可以类比归并排序中，在合并两个子列的时候所处的情况。
• 两个指针指向同一个序列，用这两个指针维护一段连续的区间或一个窗口。它们维护的是一段连续区间，这段区间满足某一个性质。可以类比于快速排序中划分区间的操作，在快速排序中将不小于某一标准的元素统一放到右侧，将不大于某一标准的元素统一放到其左侧，其维护的也是一个区间。

双指针算法的核心思想

假设有一个连续的数组，长度为n，i和j分别为游标，那么如果维护一个窗口并对这个窗口内的元素做一些操作，经典的朴素写法如下：

for (int i = 0; i < n; ++i) {
  for (int j = 0; j <= i; ++j) {
    // blablabla...
  }
}

它的时间复杂度为$O(n^2)$ 。由于双指针算法每次都要检查其合法区间，所以总的移动次数不会超过$mn$（其中m是一个常数），所以可以将上述的朴素遍历算法优化成时间复杂度为$O(n)$的双指针算法。

其本质就是通过发现某种性质，将本来应该枚举$n^2$个状态变为只需要枚举$n$个状态，就可以将$O(n^2)$变为$O(n)$的时间复杂度。

双指针算法类题目的思考方法

一般都是先从暴力的算法来思考的，先把最朴素的算法想出来或者写出来，然后进一步考察它在哪儿耗时了，然后进行改进即可。

一般上写出来的可以优化成双指针的算法的，都会有上面核心思想小节里面写的类似的代码形式。那么如何优化暴力的朴素算法呢？核心就是去找两根指针有什么规律。如果是数组下标作为指针的话，那么就只需要考虑i和j有什么规律，最常见的规律就是两根指针i和j可能存在某种单调性。

双指针算法的基本模板

下面所给出的算法模板不是一成不变的，对于不同的问题，基本写法是相似的，但是有一些部分上需要具体问题具体分析才行：

for (int l = 0, r = 0; r < n; ++r) {
  // 首先判断j要在合法的区间，所以首先就要判断j和题目所给的合法区间的关系
  // 有的时候是可能是l和r的关系；有的时候是l和n的关系，等等。
  // 并且需要判断l, r是否满足某一个性质，如果满足才能让l往前移动
  while (l <= r && check(l, r)) {
    l++;
  }
  
  // 剩下的部分具体题目具体分析其逻辑
}

在解决双指针算法类的问题时，需要明确游标谁是枚举量和谁是标记量这一重要性质。在上述模板中，描述的是：

• 上述描述的是闭区间[l, r]，且r是枚举量（每一次向右新扩展一个元素），l是标记量（标记其子区间最左边的位置）
• check(l, r)是检查子区间是否满足某一性质，如果子区间满足某一性质，则区间左边界l就会向右挪动一个位置，即表示的是子区间满足某一性质后，子区间就会缩小

双指针算法应用举例

原题链接：无重复字符的最长子串

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

示例 4:

输入: s = “”
输出: 0

提示：

0 <= s.length <= $5 * 10^4$
s 由英文字母、数字、符号和空格组成

解题思路

朴素解法

最朴素的想法，就是设置区间的左右端点的两根指针，然后再检查所在区间的字符串是否满足题目要求，如果满足，则和之前的解进行比较，谁大保存谁的。上述想法的伪代码如下：

for (int l = 0; l < n; ++l) {
  for (int r = 0; r < n; ++r) {
    if (!check(l, r)) {
      continue;
    }
    result = max(result, r - l + 1);
  }
}

优化解法

优化上述解法的关键就是查看区间端点的两根指针l和r之间的关系。设l是符合题目要求的区间的最左端点，则有：

• 当将区间右端点r所指向的元素加入到答案区间，如果出现不满足题目解的要求的情况，则一定是右端点r所指向的元素。
• 如果右端点r向右侧移动，左端点l一定也是往右侧移动，而不会出现向左侧移动的情况，使用反证法可以证明

通过上述两个性质，可以得到l和r存在单调性的结论。既然存在单调性，那么就可以将上述的朴素解法转换为更优的双指针算法的形式，伪代码如下：

for (int l = 0, r = 0; r < n; ++r) {
  while (l <= r && check(l, r)) {
    ++l;
  }
  result = max(result, r - l + 1);
}

实现代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int result = 0;
        int length = s.length();
        // hash map用来在O(1)的时间复杂度内判断某一个元素是否重复了
        unordered_map<char, int> map;

        for (int l = 0, r = 0; r < length; ++r) {
            // 如果表中已有key对应的pair，则直接数量加1，否则插入初始键值对
            if (map.count(s[r]) != 0) {
                map[s[r]] ++;
            } else {
                map.insert(pair(s[r], 1));
            }
			// 子区间中，在新加入元素后有重复的，则一定是新加入的那个元素重复了
            // 此时，维护的子区间的长度应该减少，最后停到没有重复元素的子区间的起始位置上
            while (l <= r && map[s[r]] > 1) {
                map[s[l]] --;
                l ++;
            }
			// 记录当前结果
            result = max(result, r - l + 1);
        }
        return result;
    }
};

位运算

两个常见的位运算相关问题：

• 给定一个整数n，在它的二进制表示里面，第k位数字是几
• lowbit操作

n的二进制表示中第k为是几

操作步骤：

1. 先把第k位使用右移运算移动到最后一位 x >> k
2. 看一下个位是几 x & 1

将上述两个步骤写到一起去：(n >> k) & 1，伪代码如下：

int getK(int n, int k) {
  return (n >> k) & 1;
}

lowbit(x)操作

定义一个lowbit 函数，返回参数转为二进制后，最后一个1的位置所代表的数值。即：返回x的最右边的一位1及其后紧接着的二进制数，直到末尾。它是树状数组的一个基本操作。

下面给出明确定义：

lowbit(x)表示x在二进制下最低位1代表的十进制数，假设x的最低位1是第k位（从0开始），则lowbit(x)=2^k，此时k也是末尾0的个数

举个例子，如果x = 101000， 则lowbit(x)返回的是1000；如果x = 10101， 则lowbit(x)返回的是1。

它的是实现也非常简单，就是x & -x == x & (~x + 1)， 其最简单的应用就是统计整数x的二进制表示中的1的个数，每次得到最后一位1，然后将其减掉，直到最后的值为0，统计了减了多少次就可以知道有多少个1了。证明如下:

假设x的第k位为1，根据定义lowbit有[0, k - 1]范围内的二进制值均为0，~x后，[0, k - 1]的值全为1，第k位为0，最后加上1，第k位必为1，而[0, k - 1]的值为0；由于是取反操作，[k + 1, n]上取反后的值与原值做与运算，结果为0，证毕。

实现代码如下：

int lowbit(int x) {
	return x & -x;
}

int count(int n) {
	int result = 0;	
	while ((n = n - lowbit(n)) != 0) {
		++result;
	}
	return result;
}

离散化

什么是离散化？

准确来说，是整数有序的离散化。当面临的问题所给的区间中元素个数有限，且每一个元素的值域很大的情况下，还要将它们的数值作为数组的下标来进行处理的时候，就需要用到离散化了。

由于上述情况下的集合元素的值域很大且个数有限，如：A = [1, 12, 123, 1234, 12345, 123456]，总不能开一个n = max(A)的这么大的数组来给它用，太浪费资源了，所以就需要将A中的元素映射到一个从0开始的连续的自然数集合上去，而这种映射就称为整数有序离散化。

如何操作？

在进行离散化的时候，需要注意以下问题，设待映射到从0开始的连续的自然数的集合上的集合为$A$，则有：

• $A$中的元素可能有重复，如：$\{1, 100, 2000, 2000, 30000, 30000\}$，因此需要去重。
• 如何根据$A$中的元素$x$快速计算出它的映射的值是多少？即：如何快速计算出A中的元素离散化后的值。因为集合A是有序集合，故可以使用二分来快速定位。

根据上述的两个注意事项，可以得到一个整数有序离散化的算法模板。

C++去重模板

cpp去重分为两个步骤：

• 数组排序
• 使用unique函数进行去重（unique函数要求所给数组有序，这也是为什么要先对数组排序）

vector<int> nums;
// 默认从小到大进行排序
sort(nums.begin(), nums.end());
// unique函数会将重复元素挪到末尾，并返回指向没有被移除的元素的下一个位置
// 即：指向去重后无用部分的起始位置的迭代器
nums.erase(unique(nums.begin(), nums.end()), nums.end());

二分求出x对应的离散化的值

其实就是整数二分中的寻找右半区间的起始点，即：右半区间的左端点的位置。

// nums存放的是所有带离散化的值
vector<int> nums;
int index(int x) {
  int left = 0, right = nums.size() - 1;
  
  while (left < right) {
    int mid = (left + right) / 2;
    // 要找的是第一个不小于所给值x得那个位置，即要找xxoo中的那个o的位置
    if (nums[mid] >= x) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  // 加不加1跟题目有关，如果加上1，则映射到的是[1, 10^n]，否则映射到的是[0, 10^n - 1]
  return left;
}

区间合并

区间合并的应用场景

当两个区间有交集的时候，就可以将两个区间做并集运算，将它们合并成一个大的区间。尤其需要注意边界问题：当两个区间只有端点是有交集的，也是可以合并的。

快速区间合并的过程

步骤如下：

1. 按照区间的左端点进行排序

2. 扫描整个区间，在扫描的过程当中，将所有可能有交集的区间进行合并

   • 每次维护一个当前的区间，左端点为start，右端点为end

   • 当扫描到第i个区间，考虑第i个区间和当前区间的关系

     • 第i个区间在当前区间的内部，当前区间包含第i个区间
     • 第i个区间的左端点在当前区间的内部，但是它的右端点不在当前区间的内部，与当前区间有部分交集。
     • 第i个区间在当前区间的外部，没有交集

     由于是按照左端点进行排序的，按照从小到大的次序来扫描的，所以不会出现左端点不包含在当前区间内部，而右端点包含在当前区间内部的情况。

   • 对于上述的三种情况的更新方式：

     • 第一种情况不用动
     • 第二种情况，当前区间的end坐标移动到第i个区间的右端点
     • 第三种情况，结束当前区间的扫描。将找到的区间加入到答案集合中去。并将维护的这个区间，更新成当前的第i个区间（start和end都要更新）

在上述过程中需要注意c++的一个语法点：对于pair排序，是优先以左端点排序（pair.first），再以右端点排序（pair.second）。

在实现上述算法的时候，有一个小的技巧：在维护当前区间时，可以初始化设置一个哨兵，让start = 负无穷，end = 负无穷。对于正负无穷的设置需要具体问题具体分析，一般是根据题目给的数据的范围的下界和上界，来定义负无穷和正无穷。

区间合并模板

// 将所有存在交集的区间合并
typedef pair<int, int> PII;
int merge(vector<PII>& pairs) {
    vector<PII> result;
  	// 按照左端点排序
    sort(pairs.begin(), pairs.end());
    
    const int inf = 1e9;
    int start = -inf, end = -inf;
  	
  	// 根据贪心规则来操作
    for (auto intveral : pairs) {
        int left = intveral.first, right = intveral.second;
        if (end < left) { // 没有交集
            if (start != -inf) {
                result.push_back({left, right});
            }
            start = left, end = right;
        } else { // 存在交集，进行合并
            end = max(end, right);
        }
    }
    // 上面的循环到最后，会剩下一个大的区间，这个区间没有加入到结果数组中
    // 所以需要把最后一个结果给加入进去
    if (end != -inf) {
        result.push_back({start, end});
    }
  
    // 返回的是合并后的区间总数
    return result.size();
}