目录
前言
一、移动零【做题链接】
二、复写零【做题链接】
三、快乐数【做题链接】
四、盛水最多的容器【做题链接】
五、查找总价值为目标值的两件商品【做题链接】
六、三数之和【做题链接】
七、四数之和 【做题链接】
八、有效三角形的个数【做题链接】
总结
前言
欢迎感兴趣的小伙伴交流学习。
一、移动零【做题链接】
题目代码：
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
int green_pointer = 0;
int blue_pointer = -1;
for (; green_pointer < nums.size(); green_pointer++)
{
if (nums[green_pointer] != 0)
{
blue_pointer++;
int tmp;
tmp = nums[green_pointer];
nums[green_pointer] = nums[blue_pointer];
nums[blue_pointer] = tmp;
}
}
}
};
二、复写零【做题链接】
题目代码：
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int write = arr.size() - 1;
int count_write_zore = 0;
int read;
int i = 0;
for (; count_write_zore < arr.size(); i++)
{
count_write_zore++;
if (arr[i] == 0)
{
count_write_zore++;
}
}
read = i - 1;
for (; read >= 0; read--)
{
arr[write--] = arr[read];
if (arr[read] == 0 && (read != i - 1 || count_write_zore == arr.size()))
{
arr[write--] = arr[read];
}
}
}
};三、快乐数【做题链接】
题目代码：
class Solution {
public:
int count(int n)
{
int ret=0;
while(n%10!=0||n/10)
{
ret+=pow(n%10,2);
n/=10;
}
cout<<ret<<" ";
return ret;
}
bool isHappy(int n)
{
int fast_pointer=count(count(n));
int slow_pointer=n;
while(fast_pointer!=slow_pointer)
{
fast_pointer=count(count(fast_pointer));
cout<<"(";
slow_pointer=count(slow_pointer);
cout<<")";
}
if(fast_pointer==1)
{
return true;
}
return false;
}
};四、盛水最多的容器【做题链接】
class Solution {
public:
int maxArea(vector<int>& height)
{
int left=0;
int right=height.size()-1;
int ret=0;
while(left<right)
{
ret=max(ret,(right-left)*min(height[right],height[left]));
if(height[left]<height[right])
{
left++;
}
else if(height[left]>=height[right])
{
right--;
}
cout<< ret<<" "<<left<<" ";
}
return ret;
}
};五、查找总价值为目标值的两件商品【做题链接】
class Solution
{
public:
vector<int> twoSum(vector<int>& price, int target)
{
int left=0;
int right=0;
vector<int> ret;
for(int i=0;i<price.size();i++)
{
left=i;
right=price.size()-1;
int need=target-price[i];
while(left<right)
{
if(need>price[right])
{
break;
}
else if(need<price[left])
{
break;
}
else
{
if(need==price[left]||need==price[right])
{
ret.push_back(price[i]);
if(need==price[left])
{
ret.push_back(price[left]);
}
else
{
ret.push_back(price[right]);
}
return ret;
}
left++;
right--;
}
}
}
return ret;
}
};
六、三数之和【做题链接】
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
int left = i + 1;
int right = nums.size() - 1;
int target = -nums[i];
if (i!=0&&nums[i] == nums[i - 1])
{
continue;
}
while (left < right)
{
if (target == nums[left]+ nums[right])
{
if ((left!=i+1)&&nums[left]==nums[left-1]||(right!=nums.size()-1)&&nums[right]==nums[right+1])
{
if (nums[left] == nums[left - 1])
{
left++;
}
if (nums[right] == nums[right + 1])
{
right--;
}
continue;
}
ret.push_back({ nums[i],nums[left],nums[right]});
left++;
right--;
}
else if (target > nums[left] + nums[right])
{
left++;
}
else if (target < nums[left]+ nums[right])
{
right--;
}
}
}
return ret;
}
};七、四数之和 【做题链接】
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++)
{
long long tmp1=target-nums[i];
if(i!=0&&nums[i]==nums[i-1])
{
continue;
}
for(int j=i+1;j<nums.size();j++)
{
long long tmp2=tmp1-nums[j];
if(j!=i+1&&nums[j]==nums[j-1])
{
continue;
}
int left=j+1;
int right=nums.size()-1;
while(left<right)
{
if(tmp2==nums[left]+nums[right])
{
if((left!=j+1&&nums[left]==nums[left-1])||(right!=nums.size()-1&&nums[right]==nums[right+1]))
{
if(nums[left]==nums[left-1])left++;
if(nums[right]==nums[right+1])right--;
continue;
}
ret.push_back({nums[i],nums[j],nums[left],nums[right]});
left++;
right--;
}
else if(tmp2>nums[left]+nums[right])
{
left++;
}
else if(tmp2<nums[left]+nums[right])
{
right--;
}
}
}
}
return ret;
}
};八、有效三角形的个数【做题链接】
class Solution {
public:
int triangleNumber(vector<int>& nums) {
if (nums.size() < 3) return 0;
sort(nums.begin(), nums.end());
int ret = 0;
int n = nums.size();
for (int i = n - 1; i >= 2; --i){//固定住最长的那条边
int l = 0, r = i - 1;//l,r分别代表两条边
while (l < r){
if (nums[l] + nums[r] > nums[i]){
ret += r - l;
--r;
}else{
++l;
}
}
}
return ret;
}
};总结
本文介绍了一些有关双指针的算法，一些没有描述的在最近就会补上，另外，文中图片不清晰的可以去博主码云查看【点我】
