优选算法
双指针
202. 快乐数
链接：. - 力扣（LeetCode）
【思路】
第一个实例是快乐数，因为会变为1且不断是1的循环
第二个实例不可能为1，因为会陷入一个没有1的循环
根据两个实例和鸽巢原理可以发现不断的平方和最终都会形成环，所以我们可以联想到用快慢指针，慢指针走一步，快指针走两步，最终会在环相遇，判断相遇时是否为1。
//‘平分和’操作
int squareSum(int num)
{
int sum = 0;
while(num)
{
int unit = num % 10;
num /= 10;
sum += unit*unit;
}
return sum;
}
bool isHappy(int n)
{
//快慢指针
int fast = n, slow = n;
//相遇才停下
do
{
//慢指针操作一次
slow = squareSum(slow);
//快指针操作两次
fast = squareSum(squareSum(fast));
} while(fast != slow);
//相遇的值等于1才行
return slow == 1;
}11. 盛最多水的容器
链接：. - 力扣（LeetCode）
【思路】
容量 = 底(下标相减) * 高(数组元素较小值)
如图，我们先算出最左边(1)和最右边(7)围起来的容量，然后，7不动，1继续和7的左边3，8，4...遍历算出容量，你会发现底是不断缩短的，同时高一直都是1，因为高只有两种情况，比它小或和它相等，所以1和7左边的值算出来的容量都是比1和7的容量小的，因为底在不断变小同时高可能不变也可能变小。
所以可以得出结论，每次算完容量后，元素较小的直接移动，不用遍历其他结果。
int maxArea(vector<int>& height)
{
int head = 0, tail = height.size() - 1;
int final_cap = 0;
while(head < tail)
{
//计算容量,保留较大值
int capacity = (tail - head) * min(height[head], height[tail]);
final_cap = max(final_cap, capacity);
//思路的推断移动高度小的一方
if(height[head] < height[tail])
{
++head;
}
else
{
--tail;
}
}
return final_cap;
}611. 有效三角形的个数
链接：. - 力扣（LeetCode）
【思路】
判断三角形：最长边小于其它边之和。
先排序获取单调性配合双指针解决问题。
先固定最长边，然后先从剩下的区间两端作为另外两条边，2+9>10，同时因为单调性，left的右边都比left大，所以right和左边任意一条组合都大于10，计算完组合后, right--继续找下一条边，此时2+5<10，因为单调性，right的左边都比right小，所以left和right左边的任意一条组合都小于10，排除left，left++, 继续找下一条边，这样一个区间找完就视为完成一次最大边的固定，需要固定下一条最大边，直到固定完所有最大边，最后一条最大边是倒数第三条，因为还剩最后两条构不成三角形。
int triangleNumber(vector<int>& nums)
{
//排序获取单调性
sort(nums.begin(), nums.end());
//固定一个最大边
int ret = 0;
for(int i = nums.size() - 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;
}LCR 179. 查找总价格为目标值的两个商品
链接：. - 力扣（LeetCode）
【思路】
利用单调性和双指针解决
首先相加的总和sum有三种情况，sum == target, sum < target, sum > target
先从区间两端开始，2+21<30，此时right是最大的，所以left和其他数相加只会更小，所以可以把left排除
此时left来到11的位置，11+21>30，此时left是最小的，也就意味着right和其他值相加只会更大，所以可以排除right，
vector<int> twoSum(vector<int>& price, int target)
{
vector<int> v;
//从区间两端开始
int left = 0, right = price.size() - 1;
while(left < right)
{
int sum = price[left] + price[right];
//等于
if(sum == target)
{
v = {price[left], price[right]};
break;
}
//小于
else if(sum < target)
{
++left;
}
//大于
else
{
--right;
}
}
return v;
}滑动窗口
209. 长度最小的子数组
链接：. - 力扣（LeetCode）
【思路】
当我们发现暴力解法的两个指针都可以不会退，也就是同向双指针，这时候就可以考虑使用滑动窗口思想了。
首先固定left，让right移动，不断求区间和并判断是否满足target，一旦满足你会发现right不用走了，因为right往后走虽然都满足target但是长度也在不断变大，这里利用了单调性的思想把多余的排除了，所以此时应该left往前走一步，然后继续这样判断。
int minSubArrayLen(int target, vector<int>& nums)
{
int left = 0, right = 0;
int sum = nums[right], ret = INT_MAX;
int n = nums.size();
while(left < n && right < n)
{
//移动左边
if(sum >= target)
{
ret = min(ret, right - left + 1);
sum -= nums[left++];
}
//移动右边
else
{
++right;
if(right < n)
{
sum += nums[right];
}
}
}
return ret == INT_MAX ? 0 : ret;
}
