【611.有效三角形个数】
题目描述
C++算法
双指针算法专题二：三角形个数与多数之和
双指针算法专题涵盖有效三角形个数、两数之和、三数之和及四数之和四个经典问题。核心思路包括数组排序建立单调性，利用左右指针向中间收缩或固定一端移动另一端来寻找满足条件的组合。重点讲解了两数之和类问题的指针移动条件判断，以及三数之和与四数之和中的去重技巧与递归转化逻辑。代码实现采用 C++ 标准库函数，注重边界处理与时间复杂度优化。
双指针算法专题涵盖有效三角形个数、两数之和、三数之和及四数之和四个经典问题。核心思路包括数组排序建立单调性，利用左右指针向中间收缩或固定一端移动另一端来寻找满足条件的组合。重点讲解了两数之和类问题的指针移动条件判断，以及三数之和与四数之和中的去重技巧与递归转化逻辑。代码实现采用 C++ 标准库函数，注重边界处理与时间复杂度优化。
构成三角形的条件：**设三角形三边长分别为 a（最长边），b（最短边），c。
则有 a + b > c**。
通过对三角形三边关系的分析，问题就是怎样找到三角形的最长边和最短边。解决这个问题：
我们可以先将数组元素进行排序（升序），让其满足单调性。每次固定最大值为第三边，最左边元素作为最短边，次最大值作为最长边，让最短边和最长边求和并与第三边比较。
排序（升序），降序也可。
从右往左将数组元素依次作为第三边；让左指针 left 指向最左侧元素，作为最短边；右指针 right 指向第三边左侧第一个元素，作为最长边。
***注意：***由于需要三个边构成三角形，则第三边最多为数组的第三个元素（nums[2]）。
最短边与最长边求和并与第三边比较。
**注意：
•** 由于已经按照升序排序，只要 nums[left] + nums[right] > 第三边，说明只要将左侧元素作为最短边均满足要求，则此时有满足要求的 right - left 个三角形（更新结果），然后 right--，因为 nums[left] + nums[right--] 仍有可能满足要求；
• 如果 nums[left] + nums[right] <= 第三边，则只有让 left++，才有可能让最短边与最长边之和大于第三边（right--只能让两者之和更小）。
***结束条件：***right >= left。
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 升序排序
int count = 0; // 记录三角形个数
// 从右往左依次将最大值作为第三边
for(int i = nums.size()-1; i >= 2; i--) {
int left = 0; // 左指针（最短边）
int right = i-1; // 右指针（最长边）
while(left < right) {
if(nums[left] + nums[right] > nums[i]) // 两边之和大于第三边
{
count += right-left; // 更新结果
right--; // 寻找其他可能结果
}
else left++; // 寻找与最长边相加可能大于第三边的最短边
}
}
return count;
}
};
实际就是求两数之和满足目标值，暴力算法非常简单，但可能超时。
与上一题类似我们也是结合单调性与双指针求解：
排序（默认升序），但注意数组可能已经有序（本题已经为升序数组）。
让左指针 left 指向最左边元素（最小值），右指针 right 指向最右边元素（最大值）。
两数求和，并与目标值比较：
• 和小于目标值，left++，只有这样才可能让和等于目标值（right-- 只能使得和更小）；
• 和大于目标值，right--，只有这样才有可能让和等于目标值（left++ 只能使得和更大）；
输出结果。
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left = 0, right = price.size() - 1;
while(left < right) {
if(price[left] + price[right] < target) left++;
else if(price[left] + price[right] > target) right--;
else break;
}
return {price[left], price[right]};
}
};
要 求满足要求的三数之和，我们可以这样处理：nums[i] + nums[j] + nums[k] = 0，即
nums[i] + nums[j] = -nums[k]，我们可以将 -nums[k]作为 target，这样就转化为了求两数之和的问题。
排序（默认升序）；
从左往右依次固定一个元素作为 target，并让左指针 left 指向 value 左侧元素；右指针 right 指向最右边元素。当 nums[left] + nums[right] = -target 时，即此三数满足要求（更新结果）；
• 若 和小于目标值（-target），left++，只有这样才可能让和等于目标值（right-- 只能使得和更小）；
• 若 和大于目标值（-target），right--，只有这样才有可能让和等于目标值（left++ 只能使得和更大）；
• 更新结果，让 left++，right--，继续找。
***循环条件：***left < right。
**注意：最后结果不可重复，所以需要去重：
**• 方法一：**而由于数组元素升序排序的原因，对于重复的结果，其顺序也相同。所以，我们可以用 set<vector> 来存储结果（set 可以去重）。
**• 方法二：**当更新完结果后让左指针 left 和右指针 right 跳过相同的值；同时，在固定目标值时也需要跳过相同的值。
***技巧：***由于我们按照升序排序，即单调递增，当我们固定的 target > 0（为正）时，往右所有的数肯定都已经大于 0 了，就不用找了。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 排序
vector<vector<int>> ret; // 存储结果
// 从左往右依次固定元素为 target
for(int i = 0; i < nums.size() - 2;) {
int target = nums[i]; // 目标值
int left = i + 1, right = nums.size() - 1; // 左右指针
while(left < right && target <= 0) {
if (nums[left] + nums[right] < -target) left++;
else if (nums[left] + nums[right] > -target) right--;
else {
ret.push_back({ target, nums[left], nums[right] }); // 更新结果
left++, right--; // 去重
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
i++; // 去重 target
while(i < nums.size() - 2 && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};
a + b + c + d = target
求满足要求的四个数，我们可以先依次固定一个数作为 a，那么就变成找三个的和等于
target - a，不就转化为对应三数之和的问题了。
class Solution {
public:
// 找满足三数之和的数
vector<vector<int>> threeSum(vector<int>& nums, int pos, int target_val) {
vector<vector<int>> ret; // 存储结果
// 从左往右依次固定元素为 target
int n = nums.size() - 2;
for(int i = pos + 1; i < n;) {
long target = (long)nums[i] - (long)target_val; // 目标值
int left = i + 1, right = nums.size() - 1; // 左右指针
while(left < right) {
if (nums[left] + nums[right] < -target) left++;
else if (nums[left] + nums[right] > -target) right--;
else {
ret.push_back({ nums[i], nums[left], nums[right] }); // 更新结果
left++, right--; // 去重
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
i++; // 去重 target
while(i < nums.size() - 2 && nums[i] == nums[i - 1]) i++;
}
return ret;
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end()); // 排序
vector<vector<int>> result; // 结果
// 固定一个数作为目标元素之一
int n = nums.size() - 3;
for(int i = 0; i < n;) {
auto ret = threeSum(nums, i, target - nums[i]);
if(!ret.empty()) {
// 重新完善结果
for(auto e : ret) {
e.push_back(nums[i]);
result.push_back(e);
}
}
i++; // 去重 i
while(i < nums.size() - 3 && nums[i] == nums[i - 1]) i++;
}
return result;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online