碰撞指针
# 02 碰撞指针
# 344 反转字符串 (opens new window)
编写一个函数，其作用是将输入的字符串反转过来。
输入一个字符数组，输出将其反转的字符数组
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]
解析：
本题使用双指针可以快速简单地解决。我们定义一对碰撞指针分别指向字符数组的头和尾，然后循环执行如下两步，直到两指针相遇循环终止：
- 交换 head 和 tail 指向的元素
- head 和 tail 相向移动一步
class Solution {
public:
void reverseString(vector<char>& s) {
int head = 0, tail = s.size()-1;
while(head<tail){
swap(s[head++],s[tail--]);
}
}
};
# 345 反转字符串中的元音字母 (opens new window)
给定一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。
输入一个字符串，输出一个元音字母反转后的字符串
输入：s = "lEetcode" 输出："leotcedE"
解析：
本题有两个关键任务：一是判断当前字符是否为元音字母；二是找到两个要进行反转的元音字母。
第一个任务我们使用哈希表解决，哈希表经常用于元素搜索和查重。我们定义一个哈希表存储所有的元音字母，然后使用其count方法判断字符是否为元音字母。
第二个任务我们仍采用碰撞指针解决，定义一对指针分别指向字符数组的头和尾，然后相向移动寻找元音字母。如果两指针都指向了元音字母，则交换两指针指向的元素；如果指向的不是元音字母，则向前移动。
class Solution {
public:
string reverseVowels(string s) {
vector<char> vowel{'a','e','i','o','u'};
unordered_set<char> hash;
for(const auto ch: vowel){
hash.insert(ch);
hash.insert(ch-32);
}
int head = 0, tail = s.size()-1;
while(head < tail){
if(hash.count(s[head]) && hash.count(s[tail])){
swap(s[head],s[tail]);
++head;
--tail;
}
if(!hash.count(s[head])){
++head;
}
if(!hash.count(s[tail])){
--tail;
}
}
return s;
}
};
# 680 验证回文字符串 Ⅱ (opens new window)
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
输入一个字符串，输出一个布尔值判断是否能够按照条件构成回文串
输入: s = "abca" 输出: true 解释: 可以删除c字符。
解析：
本题用碰撞指针检验回文串，检验过程分为两步：
首先，使用两个指针分别指向字符串的头和尾，逐对比较字符是否相同
如果出现不同的情况，则分别验证删除头指针指向的字符和删除尾指针指向的字符两种情况下剩余子串是否是回文字符串。任一情况成立则放回 true，否在返回 false。
根据上述我们需要一个辅助函数，能根据子串的起始和终止位置验证该子串是否是回文串。
class Solution {
public:
bool validPalindrome(string s, int start, int end){
while(start <= end){
if(s[start++]!=s[end--]){
return false;
}
}
return true;
}
bool validPalindrome(string s) {
int head = 0, tail = s.size()-1;
while(head <= tail){
if(s[head]!=s[tail]){
return (validPalindrome(s,head+1,tail) || validPalindrome(s,head,tail-1));
}
++head;
--tail;
}
return true;
}
};
# 167 两数之和 II - 输入有序数组 (opens new window)
在一个增序的整数数组里找到两个数，使它们的和为给定值，已知有且只有一对解。
输入是一个数组（numbers）和一个给定值（target），输出是两个数的位置，从 1 开始计数。
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
解析：
本题和1 两数之和 (opens new window)的区别在于输入的是有序数组。
因为数组已经排好序，我们可以采用碰撞指针来寻找这两个数字，一个指向数组开头 head，一个指向数组末尾 tail。判断这两个指针指向的元素之和 TwoSum 与 target 值的关系：
- 如果大于 target 则将 tail 向左移动获取更小的两数之和；
- 如果小于 target 则将 head 向右移动获取更大的两数之和；
- 如果与 target 值相等则 head 和 tail 指向的元素为所找的一对解
对于排好序且有解的数组，双指针一定能以 O(n) 时间复杂度遍历到最优解。碰撞指针缩减搜索空间的关键在于它每一次移动指针都直接排除了一行或一列的搜索空间，例如当TwoSum = numbers[head]+numbers[tail] < target这时就将head++，因为tail已经对应的是最大值无需再去搜索本行中其他解，这样就直接排除了当前一行的搜索空间；同理，TwoSum = numbers[head]+numbers[tail] > target时就将tail--，此时head对应的是当前最小值也无需去搜索本列中其他解，这样就直接排除了head当前一列的搜索空间。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int head = 0, tail = numbers.size()-1;
while(head<tail){
int sum = numbers[head] + numbers[tail];
if(sum > target){
--tail;
}else if(sum < target){
++head;
}else{
return {head+1,tail+1};
}
}
return {};
}
};
# 633 平方数之和 (opens new window)
给定一个非负整数 c ，判断是否存在两个整数 a 和 b，使得 a2 + b2 = c
输入一个整数，输出一个布尔值表示该值是否为两个整数的平方和
输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5
解析：
本题是167 两数之和 II - 输入有序数组 (opens new window)的变种题。
我们用碰撞指针遍历数组空间为[0,sqrt(c)]的范围：
- 如果大于 target 则将 tail 向左移动获取更小的两数平方和；
- 如果小于 target 则将 head 向右移动获取更大的两数平方和；
- 如果与 target 值相等则 head 和 tail 指向的元素为所找的一对解
需要注意的是，因为测试用例范围很大，用长整型存储结果
class Solution {
public:
bool judgeSquareSum(int c) {
long head = 0;
long tail = (int)sqrt(c);
while(lsh<=rsh){
long sum = pow(head,2) + pow(tail,2);
if(sum == c){
return true;
}else if(sum > c){
--tail;
}else{
++head;
}
}
return false;
}
};
# 15 三数之和 (opens new window)
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请找出所有和为 0 且不重复的三元组。
输入一个一维数组，输出一个二维数组包含所有和为 0 且不重复的三元组
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
解析：
本题我们可以将三数之和转化为167 两数之和 II - 输入有序数组 (opens new window)，即 a + b = -c。将 -c 转化 target 在除 c 之外的元素中寻找 a 和 b。当然要采用和 167 相同的碰撞指针解决本题，我们要对数组进行排序才能有双指针。所以本题主要有如下两个任务：
- 对数组进行排序，使得可以使用双指针找两数之和
- 遍历每个元素，在数组中位于该元素之后的所有元素中寻找两数之和为当前元素值相反数的两个数，如果存在则构成一个三元组。这里我们需要考虑一个问题：为什么只用考虑该元素之后的元素，而不需要考虑之前遍历过的元素？因为如果之前的元素和当前元素能够构成三数之和为 0，那么该结果在遍历前面的元素时就已经加入了结果集，如果再考虑就会产生重复的三元组。
本题最为关键的就是结果去重，不仅要考虑到外层循环遍历相同元素产生的重复结果，还要考虑到双指针在遍历过程中如果前后遍历到相同元素也会产生重复结果。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 数组长度小于3，无法构成三元组
int len = nums.size();
vector<vector<int>> ans;
if(len < 3){
return ans;
}
// 排序数组
sort(nums.begin(),nums.end());
// 如果数组最小的元素都大于零，那么无法构成 a + b + c = 0
if(nums[0] > 0){
return ans;
}
for(int i=0;i<len;++i){
// 外层遍历去重，遍历到相同的元素会产生重复结果
if(i>0 && nums[i] == nums[i-1]){
continue;
}
// 双指针寻找两数之和
int head = i+1, tail = len-1;
while(head<tail){
int sum = nums[head] + nums[tail];
if(sum == -nums[i]){
ans.push_back({nums[i],nums[head++],nums[tail--]});
// 双指针遍历去重，如果双指针前后遍历到相同元素也会产生重复结果
while(head<tail && nums[head] == nums[head-1]){
++head;
}
while(head<tail && nums[tail] == nums[tail+1]){
--tail;
}
}else if(sum > -nums[i]){
--tail;
}else{
++head;
}
}
}
return ans;
}
};
# 18 四数之和 (opens new window)
给定一个由 n 个整数组成的数组 nums ，和一个目标值 target 。找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
输入一个数组和一个整型值，输出一个二维数组包含不重复的和为目标值的四元组
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
解析：
本题本质上和15 三数之和 (opens new window)一样，还是使用循环+双指针的思路去找到和为目标是 target 的四元组。
本题更加复杂的地方在于：三数之和中双指针寻找的 target 为循环中遍历值的相反数，是一个确定值；而四数之和中双指针寻找的 subTarget 是给定的目标值 target 减去两数之和后的一个不确定的值，我们需要再在外层嵌套一层循环，用两个 for 循环去遍历这两个数的所有组合形成的 subTarget。
基于上述思路本题解题思路如下：
- 对数组排序
- 双层循环遍历
subTarget = target - (nums[c] + nums[d])的所有情况 - 在循环内使用双指针寻找两数之和为 target
同样需要注意去重问题。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int len = nums.size();
vector<vector<int>> ans;
if(len < 4){
return ans;
}
// 排序数组
sort(nums.begin(), nums.end());
for(int i=0;i<len;++i){
// 外层遍历去重复
if(i>0 && nums[i] == nums[i-1]){
continue;
}
for(int j=i+1;j<len;++j){
// 外层遍历去重复
if(j>i+1 && nums[j] == nums[j-1]){
continue;
}
// 双指针寻找两数和为 subTarget
int subTarget = target - nums[i] - nums[j];
int head = j+1, tail = len-1;
while(head<tail){
int sum = nums[head] + nums[tail];
if(sum == subTarget){
ans.push_back({nums[i],nums[j],nums[head++],nums[tail--]});
// 双指针遍历去重复
while(head<tail && nums[head] == nums[head-1]){
++head;
}
while(head<tail && nums[tail] == nums[tail+1]){
--tail;
}
}else if(sum > subTarget){
--tail;
}else{
++head;
}
}
}
}
return ans;
}
};
# 27 移除元素 (opens new window)
给定一个数组 nums 和一个值 val，要求原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
输入一个数组和一个值，输出一个整型值表示按条件操作数组之后的新长度
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
解析：
本题要求在 O(1) 的空间复杂度内完成，数组元素的顺序可以改变，并且不需要考虑数组中超出新长度后面的元素。所以本题可以考虑使用碰撞指针完成。
我们定义两个指针 head 和 tail 分别指向数组的头和尾并相向移动，然后按如下两个步骤移动指针：
- 先移动 tail 如果指向的元素等于 val，则继续移动直到指向的元素值不为 val
- tail指向的元素不为 val，转过来看 head 指向的元素。如果 head 指向的元素值不为 val 则移动指针；如果其指向的元素刚好为 val 则将当前 tail 指向的元素覆盖到 head 指向的位置，并同时移动两指针。
总的来说就是 head 找需要删除的元素， tail 找不用被删除的元素，然后用 tail 覆盖 head，并继续该操作直到两指针相遇。
上诉思路可以进一步简化：上面的思路中我们用 tail 取寻找不等于 val 的元素，可以通过改变指针的移动规则省略这一步骤。不论 tail 值是否为 val，在 head 找到 val 时我们就用 tail 指向的元素覆盖，完成覆盖后只移动 tail 而不移动 head。这样就可以再次判断覆盖的值是否为 val，直到用于覆盖的值不为 val 时，head 才向前移动。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int head = 0, tail = nums.size();
while(head < tail){
if(nums[head] == val){
nums[head] = nums[--tail];
}else{
++head;
}
}
return head;
}
};