- 对撞指针是双指针算法之一。
- 对撞指针从两端向中间迭代数组。一个指针从始端开始,另一个从末端开始。
- 对撞指针的终止条件是两个指针相遇。
- 对撞指针常用于排序数组。
167. 两数之和 II - 输入有序数组
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return {left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {-1, -1};
}
};
27. 移除元素
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right-1];
right--;
} else {
left++;
}
}
return left;
}
};
125. 验证回文串
class Solution {
public:
bool isPalindrome(string s) {
string sgood;
for (char ch: s) {
if (isalnum(ch)) {
sgood += tolower(ch);
}
}
int n = sgood.size();
int left = 0, right = n - 1;
while (left < right) {
if (sgood[left] != sgood[right]) {
return false;
}
++left;
--right;
}
return true;
}
};
11. 盛最多水的容器
class Solution {
public:
int maxArea(vector<int>& height) {
int res = 0, i = 0, j = height.size() - 1;
while (i < j) {
res = max(res, min(height[i], height[j]) * (j - i));
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return res;
}
};
- leetcode 对撞指针 解法题目
- 7. 整数反转(easy)
- 9.回文数(easy)
- 27.移除元素(easy)
- 125.验证回文串(easy)
- 167.两数之II-输入有序数组(easy)
- 190.颠倒二进制位(easy)
- 344.反转字符串(easy)
- 345.反转字符串中的元音字母(easy)
- 11.盛水最多的容器(medium)