• 本人的LeetCode账号：魔术师的徒弟，欢迎关注获取每日一题题解，快来一起刷题呀~
• 本人Gitee账号：路由器，欢迎关注获取博客内容源码。
  

  文章目录

  • 一、盛水最多的容器
  • 二、三数之和
  • 三、最接近的三数之和
  • 四、四数之和

一、盛水最多的容器

   本题的双指针思路是首先两个指针一个指向最左边，另一个指向最右边，开始；

  每一轮都让当前的面积与ret取最大值，然后比较height[l]和heght[r]:

• 若height[l] < height[r],则所有以height[l]为左边的体积都会小于等于当前面积，所以此时可以舍弃l做左边的机会，让++l
• 反之同理，--r

代码：

class Solution {
public:
int maxArea(vector<int>& height)
{
int ret = 0;
int n = height.size();
int l = 0, r = n - 1;
while (l < r)
{
int area = (r - l) * min(height[l], height[r]);
ret = max(ret, area);
if (height[l] < height[r])
{
/*如果左边小 那么l++ 去掉所有可能以height[l]为容器高度的矩形
因为这些矩形一定小于等于当前面积*/
l++;
}
else
{
r--;
}
}
return ret;
}
};

二、三数之和

  总体思路就是在有序数组中，固定一个数，然后另外两个数就变成了找两数之和的双指针，注意有序时采用的去重方法：if (k > 0 && nums[k] == nums[k - 1]) while (i < j && nums[i - 1] == nums[i]) while (i < j && nums[j + 1] == nums[j])

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
// 先排序 
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
int n = nums.size();
for (int k = 0; k < n - 2; ++k)
{
// 如果当前的nums[k]大于0了 因为排了序 后面再选两数必然比0大
// 不可能达到等于0
if (nums[k] > 0) break;
// 如果和前面一个一样 那么得到的结果也会一样 就别找了 避免重复
if (k > 0 && nums[k] == nums[k - 1]) continue;
int i = k + 1, j = n - 1;
// 两个指针 现在k固定了 并且后面数组有序
// 如果和大于0 则只能让和变小 就得让j--
// 如果和小于0 则只能让和变大 就得让i++
// 记得每次去掉重复组
while (i < j)
{
int sum = nums[k] + nums[i] + nums[j];
if (sum == 0)
{
ret.push_back({nums[k], nums[i], nums[j]});
i++;
j--;
// 去掉去掉重复的元素
while (i < j && nums[i - 1] == nums[i]) ++i;
while (i < j && nums[j + 1] == nums[j]) --j;
}
else if (sum > 0)
{
--j;
// 去掉重复元素
while (i < j && nums[j + 1] == nums[j]) --j;
}
else
{
++i;
// 去掉重复元素
while (i < j && nums[i - 1] == nums[i]) ++i;
}
}
}
return ret;
}
};

三、最接近的三数之和

  本题思路与上题类似，注意若sum的距离比最后要返回的ans的距离进，则及时更新ans，如果结果大于target，则j--;如果结果小于target,则i++,如果结果等于target则返回target，本题不需要考虑重复的情况。

class Solution {
public:
int threeSumClosest(vector<int>& nums, int target)
{
// 一样先排序 然后固定一个数 因为本题要找的是与target最接近的三个数的和
// 可以用ans 若abs(sum - target) < abs(ans - target) 则更新ans = sum
sort(nums.begin(), nums.end());
int n = nums.size();
// 先初始化成前三个数的和
int ans = nums[0] + nums[1] + nums[2];
for (int k = 0; k < n - 2 ; ++k)
{
// 固定k双指针i j
int i = k + 1, j = n - 1;
while (i < j)
{
int sum = nums[k] + nums[i] + nums[j];
if (abs(sum - target) < abs(ans - target))
{
ans = sum;
}
if (sum == target) return target;
else if (sum > target)
{
--j;
}
else
{
++i;
}
}
}
return ans;
}
};

四、四数之和

  本题的思路是由三数之和衍生而来，排序数组后固定两个数，然后另外两个数使用双指针算法，注意和之前类似的去重技巧即可。

typedef long long LL;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int a = 0; a < n - 3; ++a)
{
// 去重
if (a > 0 && nums[a] == nums[a - 1]) continue;
for (int b = a + 1; b < n - 2; ++b)
{
// 去重
if (b > a + 1 && nums[b] == nums[b - 1]) continue;
int c = b + 1, d = n - 1;
while (c < d)
{
LL sum = (LL)nums[a] + (LL)nums[b] + (LL)nums[c] + (LL)nums[d];
if (sum == target)
{
ret.push_back({nums[a], nums[b], nums[c], nums[d]});
++c;
--d;
while (c < d && nums[c - 1] == nums[c]) ++c;
while (c < d && nums[d + 1] == nums[d]) --d;
}
else if (sum > target)
{
--d;
while (c < d && nums[d + 1] == nums[d]) --d;
}
else
{
++c;
while (c < d && nums[c - 1] == nums[c]) ++c;
}
}
}
}
return ret;
}
};

最后

以上就是默默可乐为你收集整理的LeetCode双指针算法总结1一、盛水最多的容器二、三数之和三、最接近的三数之和四、四数之和的全部内容，希望文章能够帮你解决LeetCode双指针算法总结1一、盛水最多的容器二、三数之和三、最接近的三数之和四、四数之和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。