本文记录作者刷题过程中与双指针相关的题目。
1、删除数组中的元素
（1）删除数组中的某个（所有的）目标值
27. 移除元素（简单难度）
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n=nums.size();
// 数组中至少有0个元素
int slow=0; // 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
int fast = 0;// 快指针，负责遍历整个数组
while(fast < n)
{
//快指针不等于目标值时
if (nums[fast] != val)
{
nums[slow] = nums[fast];//快指针指向的数覆盖给慢指针指向的数
slow++;//慢指针+1
fast++; //快指针+1
}
// 快指针等于目标值时，快指针+1
else{
fast++;//快指针+1
}
}
return slow;//返回慢指针
}
};
（2）删除有序数组中的重复项
26. 删除有序数组中的重复项（简单难度）
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n=nums.size();
if(n==0) return 0;
// 数组中至少有1个元素
int slow=1;// 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
int fast=1;// 快指针，负责遍历整个数组
while(fast<n){
// 快指针和上一个元素不同时，
if(nums[fast]!=nums[slow-1]){
nums[slow]=nums[fast];// 快指针元素覆盖慢指针元素
slow++;//慢指针前进
fast++;//快指针前进
}
// 快指针和上一个元素相同时，快指针前进
else{
fast++;
}
}
return slow;
}
};
80. 删除有序数组中的重复项 II（中等难度）
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n=nums.size();
if(n<=2) return n;
// 数组中至少有2个元素
int slow=2;// 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
int fast=2;// 快指针，负责遍历整个数组
while(fast<n){
// 快指针不等于
if(nums[fast]!=nums[slow-2]){
nums[slow]=nums[fast];
slow++;
fast++;
}
else{
fast++;
}
}
return slow;
}
};
2、移动数组中的元素
283. 移动零（简单难度）
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n=nums.size();
// 数组中至少有0个元素
int slow=0;// 慢指针,[0,low),指向移动后的区间的最后一个元素的后一个索引
int fast=0;// 快指针，负责遍历整个数组
while(fast<n){
// 如果快指针不为0
if(nums[fast]!=0){
swap(nums[slow],nums[fast]);// 快慢交换
slow++;
fast++;
}
else{
fast++;
}
}
}
};
75. 颜色分类（中等难度）
class Solution {
public:
void sortColors(vector<int>& nums) {
int n=nums.size();
if(n<2) return;
// 整个数组需要分成3个区间:
int zero = 0;//[0,zero)，红色元素,存放0
int one = 0;//[zero,one)，白色元素，存放1,同时负责遍历
int two = n-1;// [one,two)，篮色元素，存放2
while (one < n) {
// 如果当前元素==0,移动到头部
if (nums[one] == 0&&zero<one) {
swap(nums[one], nums[zero]);//
zero++;
}
// 如果当前元素==2,移动到表尾
else if (nums[one] == 2&& one<two) {
swap(nums[one], nums[two]);
two--;
}
// 如果当前元素==1，跳过
else {
one++;
}
}
//quickSort(nums,0,nums.size()-1);
}
}
215. 数组中的第K个最大元素（中等难度）
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int len = nums.size();
return quickFind(nums,k-1,0,len-1);//从大到小排序，第k大就是第k-1个索引，返回第k-1个索引的值
}
// 快排法
int quickFind(vector<int>& nums, int k,int left,int right){
int index = partition(nums,left,right);//开始分区
// 结束分区
if(index==k){
return nums[index];//first是基准值索引，表示第first个
}
else if(index>k){
return quickFind(nums, k,left,index-1);
}
else {
return quickFind(nums, k,index+1,right);
}
}
// 分区函数
int partition (vector<int> &nums, int first, int last) {
int key = nums[first];//默认第一个为基准值
while (first < last) {
// 从右往左找到第一个小于key的值
while (first < last && nums[last] <= key) --last;
nums[first] = nums[last];
// 从左往右找到第一个大于key的值
while (first < last && nums[first] >= key) ++first;
nums[last] = nums[first];
}
nums[first] = key;// 基准值归位
return first;// 返回索引
}
};
905. 按奇偶排序数组（简单难度）
class Solution {
public:
/*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
左指针寻找奇数值，右指针寻找偶数值，当符合交换条件时，进行两数交换；
否则指针继续左右运动，寻找符合条件的奇偶值。
当两指针相遇时，结束循环。*/
vector<int> sortArrayByParity(vector<int>& nums) {
int left=0;//左指针
int right=nums.size()-1;//右指针
// 遍历数组[left,right],
while(left<right){
// 如果左指针指向奇数，右指针指向偶数，就交换两个数
if (nums[left] % 2 > nums[right] % 2) {
swap(nums[left],nums[right]);
}
// 如果左指针指向偶数，左指针移动
if (nums[left] % 2 == 0) left++;
// 如果右指针指向奇数，右指针移动
if (nums[right] % 2 == 1) right--;
}
return nums;
}
};
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面（简单难度）
class Solution {
public:
/*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
左指针寻找偶数值，右指针寻找奇数值，当符合交换条件时，进行两数交换；
否则指针继续左右运动，寻找符合条件的奇偶值。
当两指针相遇时，结束循环。*/
vector<int> exchange(vector<int>& nums) {
int left=0;//左指针
int right=nums.size()-1;//右指针
// 遍历数组[left,right],
while(left<right){
// 如果左指针指向偶数，右指针指向奇数，就交换两个数
if (nums[left] % 2 < nums[right] % 2) {
swap(nums[left],nums[right]);
}
// 如果左指针指向奇数，左指针移动
if (nums[left] % 2 == 1) left++;
// 如果右指针指向偶数，右指针移动
if (nums[right] % 2 == 0) right--;
}
return nums;
}
};
922. 按奇偶排序数组 II（简单难度）
class Solution {
public:
/*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
遍历所有偶数索引*/
vector<int> sortArrayByParityII(vector<int>& nums) {
//
int n = nums.size();
int j = 1;//奇数索引
// 遍历整个数组的所有偶数索引
for (int i = 0; i < n; i += 2) {
// 如果偶数索引上的数是奇数
if (nums[i] % 2 == 1) {
// 连续遍历整个数组的所有奇数索引，找到一个数是偶数
while (nums[j] % 2 == 1) j += 2;
swap(nums[i], nums[j]);//交换两个数
}
}
return nums;
}
};
3、查找排序数组中的2个数
剑指 Offer 57. 和为s的两个数字（简单难度）
剑指 Offer II 006. 排序数组中两个数字之和（简单难度）
class Solution {
public:
/*解析：这道题在一个排序数组中查找2个数，使其和为target
提到排序，可能会选用二分查找法，二分查找法确实可以结合使用
但是这道题难度简单，用普通的双指针就可以搞定
排序数组的特点可以作为移动左右指针的依据，和较小右移左指针，和较小左移右指针
*/
vector<int> twoSum(vector<int>& nums, int target) {
int left=0;//左指针
int right=nums.size()-1;//右指针
int sum=0;
while(left<=right){
sum=nums[left]+nums[right];
// 如果两数和==target，直接返回
if(sum==target) return {nums[left],nums[right]};
// 如果两数和>target，说明应该降低两数和，右指针左移即可
else if(sum>target) right--;
// 如果两数和<target，说明应该增加两数和，左指针右移即可
else left++;
}
return {nums[left],nums[right]};
}
};
4、其他问题
977. 有序数组的平方（简单难度）
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n=nums.size();
vector<int> res(n,0);
int k=n-1;
int left=0;
int right=n-1;
while(left<=right){
// 左右指针，谁大加谁
if((nums[left]*nums[left])<(nums[right]*nums[right])) {
res[k--]=nums[right]*nums[right];
right--;
}
else{
res[k--] = nums[left]*nums[left];
left++;
}
}
return res;
}
};
169. 多数元素（简单难度）
class Solution {
public:
int majorityElement1(vector<int>& nums) {
// 统计nums中每个数组元素出现的频率
unordered_map<int,int> dict;// nums中每个数，出现频率
for(int num:nums) dict[num]++;
//建立哈希数组找其中出现次数大于n/2的数
int n=nums.size();
for(auto it=dict.begin();it!=dict.end();++it){
if(it->second>n/2)
return it->first;
}
return 0;
}
// 方法二
int majorityElement(vector<int>& nums) {
if (nums.size()==1) return nums[0];
//排序
sort(nums.begin(),nums.end());
vector<int> res;
// 使用双指针查找所有可能的众数
int cur=0;//当前数
int count=0;//计数器
int maxCount=0;//最大计数
int slow=0; //慢指针
int fast=1;// 快指针
//统计前一个数和后一个数相同的频率
while(fast<nums.size()){
//如果当前数与前一个数相同
if(nums[fast]==nums[slow]) {
count++;
cur= nums[fast];//记录快指针手中的数
slow++;
fast++;
}
//如果当前数与前一个数不相同
else{
count=1;
slow++;
fast++;
}
//如果计数超过最大计数
if(count>maxCount){
maxCount=count;//更新最大计数
res.clear();//清空众数数组（之前的失效）
res.push_back(cur);//将当前数加入众数数组
}
//如果计数等于最大计数
else if(count==maxCount){
res.push_back(cur);//将当前数加入众数数组
}
}
return res[0];
}
};
941. 有效的山脉数组
class Solution {
public:
bool validMountainArray(vector<int>& arr) {
int N = arr.size();
int i = 0;
// 递增扫描
while (i+1<N&&arr[i]<arr[i+1]) i++;
// 最高点不能是数组的第一个位置或最后一个位置
if(i==0||i==N-1) return false;
// 递减扫描
while(i+1<N&&arr[i]>arr[i + 1]) i++;
return i == N-1;
}
};
189. 轮转数组
class Solution {
public:
// 方法一：使用额外数组
void rotate1(vector<int>& nums, int k) {
int n=nums.size();
vector<int> res(n);
int j=0;
for(int i=0;i<n;i++){
j=(i+k)%n;
res[j]=nums[i];
}
nums.assign(res.begin(), res.end());
}
// 方法二：数组反转
void rotate(vector<int>& nums, int k) {
int n=nums.size();// 1 2 3 4 5 6 7,k=3
k = k%n;
reverse(nums.begin(), nums.end());// 反转[0,n-1] 7 6 5 4 3 2 1
reverse(nums.begin(), nums.begin()+k);// 反转[0,k-1] 5 6 7 4 3 2 1
reverse(nums.begin()+k, nums.end());// 反转[k,n-1] 5 6 7 1 2 3 4
}
};
11. 盛最多水的容器
class Solution {
public:
/* 左右指针分别从数组两端出发，容量的高为min(height[left],height[right])
容量的长为right-left，则容量可以计算出来
移动左右指针时，谁小移动水*/
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int res = 0;
while (left < right) {
int area =min(height[left], height[right])*(right-left);
res = max(res, area);
if (height[left]<= height[right]) ++left;
else --right;
}
return res;
}
};
238. 除自身以外数组的乘积
class Solution {
public:
/*原 数组： [1 2 3 4]
左部分的乘积： 1 1 1*2 1*2*3
右部分的乘积： 2*3*4 3*4 4 1
结 果：1*2*3*4 1*3*4 1*2*4 1*2*3*1*/
vector<int> productExceptSelf(vector<int>& a) {
int n=a.size();
vector<int> res(n,1);
// 左遍历
int left=1;// [0,i-1]的累乘
for(int i=0;i<n;i++){
res[i]=left;
left*=a[i];
}
// 右遍历
int right=1;// [i+1,n-1]的累乘
for(int i=n-1;i>=0;i--){
res[i]*=right;
right*= a[i];
}
return res;
}
};
392. 判断子序列
bool isSubsequence(string s, string t) {
int n = s.length(), m = t.length();
int i = 0, j = 0;
while (i<n&&j<m) {
if (s[i] == t[j]) i++;
j++;
}
return i == n;
}
581. 最短无序连续子数组
class Solution {
public:
/*从左往右遍历,max记录的是0到i最大的数，
如果第i个位置比max小，证明第i位置元素不正确，
因为它前面有个比它大的数,记录下标high=i
从右往左遍历，min记录的是n-1到i最小的数，
如果第i位置元素比min大，证明第i位置元素不正确,
因为它后面有比它小的数，记录下标low=i
区间[low,high]即为所求*/
int findUnsortedSubarray(vector<int>& nums) {
int n=nums.size();
if(n<=1) return 0;
int max=nums[0];// 记录正序遍历中的最大值
int min=nums[n-1];// 记录反序遍历中的最小值
int low=1,high=0;// 最短无序连续子区间就是[low,high]
for(int i=1;i<=n-1;++i){
if(nums[i]>=max) max=nums[i];// 注意=
else high=i;
}
for(int i=n-2;i>=0;--i){
if(nums[i]<=min) min=nums[i];// 注意=
else low=i;
}
// 子区间可能不存在，需要讨论
return low<=high?high-low+1:0;
}
};