力扣编程题算法初阶之双指针算法+代码分析

class Solution
{
public:int bitSum(int n)int sum = 0;while (n){int t = n % 10;sum += t * t;n /= 10;}bool isHappy(int n){int slow = n, fast = bitSum(n);while (slow != fast){slow = bitSum(slow);fast = bitSum(bitSum(fast));}return slow == 1;}
};

第三题：盛水最多的容器

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路：

第一想法就是暴力枚举

s=h（高）*w（宽度）

即弄两个for循环，依次求出面积，再比较最大值，这样时间复杂度为n的平方会超时，因此

第二种就是双指针，观察发现，面积的高是由左右两边的低边界为准。就以上图为例，高是由右边那条高决定，左边高往右移动由于w一定减小，h要么减小要么不变，那么面积一定减小，所以我们就从两个边界开始来移动，记录每一次的面积，返回最大即可

注意，每次移动的是那个h小的，因为大h移动，s要么减少要么不变，而我们求的是最大的。

第一种：暴力求解

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int ret = 0;// 两层 for 枚举出所有可能出现的情况for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 计算容积，找出最⼤的那⼀个ret = max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
};

第二种：

对撞指针：

class Solution
{
public:int maxArea(vector<int>& height){int left = 0, right = height.size() - 1, ret = 0;while (left < right){int v = min(height[left], height[right]) * (right - left);ret = max(ret, v);// 移动指针if (height[left] < height[right]) left++;else right--;}return ret;}
};

第四题：有效三角形的个数

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路：

在判断一个三角形时，如果对于一对升序数组a,b,c

如果a+b>c那么即可构成三角形，不需要判断三次

原因，如果上述条件成立那么，b+c>a,a+c>b一定成立，因为c是最大的数

第一思路就是暴力求解，先把给定数组排序，然后从第一个元素开始遍历，用三个for循环实现，但是时间复杂度较大，运行会超时

class Solution {
public:int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 2. 从⼩到⼤枚举所有的三元组for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {// 当最⼩的两个边之和⼤于第三边的时候，统计答案if (nums[i] + nums[j] > nums[k])ret++;}}}return ret;}
};

应次这里换一种高效方法就是用双指针来实现，因为已经排完升序，依据暴力解法，可以先固定一条最长边，然后找出比这条边小的二元组，让着个二元组的和大于最长边，即可利用对撞指针来实现。

class Solution
{
public:int triangleNumber(vector<int>& nums){// 1. 优化sort(nums.begin(), nums.end());// 2. 利⽤双指针解决问题int ret = 0, n = nums.size();for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数{// 利⽤双指针快速统计符合要求的三元组的个数int left = 0, right = i - 1;while (left < right){if (nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;}
};