Two Sum
实际上正规的教科书上并没有双指针这种算法，只不过在做题的过程中我们总结出了一大类问题，可以通过两根指针来解决，这类问题最经典的要属56. 两数之和。这是一个最经典的问题，大家可能都有遇到过，由此引申出57. 三数之和和58. 四数之和，两数和的问题可以通过更简单的哈希表方法去做，所以我们来看一下三数和的解法，代码如下。
class Solution {
public:
/**
* @param numbers: Give an array numbers of n integer
* @return: Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int>> threeSum(vector<int> &numbers) {
// write your code here
if (numbers.size() < 3) {
return {};
}
vector<vector<int> > res;
sort(numbers.begin(), numbers.end());
for (int i = 0; i < numbers.size(); ++i) {
if (i && numbers[i] == numbers[i - 1]) {
continue;
}
int target = -numbers[i];
int left = i + 1;
int right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum < target) {
++left;
}
else if (sum > target) {
--right;
}
else {
res.push_back({numbers[i], numbers[left], numbers[right]});
++left;
while (numbers[left] == numbers[left - 1]) ++left;
}
}
}
return res;
}
};
这题的解法就是先固定一个点，再用左右两根指针，从数列头和尾开始遍历，因为数组是排好序的，所以根据这三个位置的和与target的关系移动指针，就可以找到解了。
补充问题：
443. 两数之和 II
533. 两数和的最接近值
587. 两数之和 - 不同组成
609. 两数和-小于或等于目标值
交叉链表与带环链表
380. 两个链表的交叉这类问题需要求解两个交叉链表的交点，首先我们通过一次遍历求出两根链表的长度差，再让长链表的指针先跑这个长度差，再让两根指针同时跑，这样当两根指针跑到一起的时候，这个位置就是我们要找的交点。下面给出代码。
class Solution {
public:
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
ListNode * getIntersectionNode(ListNode * headA, ListNode * headB) {
// write your code here
if (headA == NULL or headB == NULL) {
return NULL;
}
int lenA = 0, lenB = 0;
ListNode * pA = headA;
ListNode * pB = headB;
while (pA != NULL) {
pA = pA->next;
++lenA;
}
while (pB != NULL) {
pB = pB->next;
++lenB;
}
if (lenA > lenB) {
int diff = lenA - lenB;
for (int i = 0; i < diff; ++i) {
headA = headA->next;
}
}
if (lenB > lenA) {
int diff = lenB - lenA;
for (int i = 0; i < diff; ++i) {
headB = headB->next;
}
}
while (headA and headB) {
if (headA == headB) {
return headA;
}
headA = headA->next;
headB = headB->next;
}
return NULL;
}
};
有这个问题引申出一类可以通过快慢指针解决的链表问题，如228. 链表的中点，可以设置两根指针，一根快指针每次移动两个单位，一根慢指针每次移动一个单位，这样当快指针跑到链表结尾时，慢指针指向的就是链表的中点了。
同样的102. 带环链表，103. 带环链表 II也使用了快慢指针法，103这个题让与228题一样的两根快慢指针在链表上跑，当两根指针相遇时，让其中一根重新回到链表头，当他们第二次相遇时的位置便是环的起始点，这实际上在数学上可以给出证明，这里不再赘述。
去除重复元素
521. 去除重复元素，这个问题要求去除数组中的重复元素，且在原数组上进行操作。第一步我们要对数组进行排序，然后用两根指针，第一根i指针遍历这个数组，第二根m指针指向当前最后一个不重复的位置，然后比较两根指针，当所指位置元素不同时，将nums[i]赋给nums[++m]（同时自增1），代码如下。
class Solution {
public:
/**
* @param nums: an array of integers
* @return: the number of unique integers
*/
int deduplication(vector<int> &nums) {
// write your code here
int n = nums.size();
int m = 0;
if (n == 0) {
return 0;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < n; ++i) {
if (nums[i] != nums[m]) {
nums[++m] = nums[i];
}
}
return m + 1;
}
};
烙饼排序
894. 烙饼排序是一个很有意思的问题，对一个数组，只能进行一种翻转操作flip，flip(arr, i): 翻转数组中下标从 0 到 i 的元素。与传统的排序算法不同，传统的排序算法试图以尽可能少的比较进行排序。我们的目标是用尽可能少的翻转来实现排序，代码如下。
class Solution {
public:
/**
* @param array: an integer array
* @return: nothing
*/
void pancakeSort(vector<int> &array) {
// Write your code here
int n = array.size();
vector<int>::iterator it;
for (int i = n; i >= 1; --i) {
it = std::max_element(array.begin(), array.begin() + i);
if (it != array.begin() + i - 1) {
FlipTool::flip(array, it - array.begin());
FlipTool::flip(array, i - 1);
}
}
}
};
网友评论