C++算法
C++ 双指针算法实战：有效三角形个数与和为 S 的两个数字
讲解 C++ 双指针算法在两个经典问题中的应用。第一部分通过排序和对撞指针计算有效三角形个数，优化了传统验证逻辑。第二部分针对升序数组，使用对撞指针查找和为指定值的两个数字。内容涵盖题目描述、解题思路、核心代码实现及测试示例，帮助理解双指针在数学组合问题中的具体实践。
讲解 C++ 双指针算法在两个经典问题中的应用。第一部分通过排序和对撞指针计算有效三角形个数，优化了传统验证逻辑。第二部分针对升序数组，使用对撞指针查找和为指定值的两个数字。内容涵盖题目描述、解题思路、核心代码实现及测试示例，帮助理解双指针在数学组合问题中的具体实践。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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
a + b > c（其中 a, b, c 从小到大）即可。nums[k] 作为三角形的第三边，然后在 [0, k-1] 范围内使用对撞指针寻找满足条件的两边。
left = 0 和 right = k-1。nums[left] + nums[right] > nums[k] 时，由于数组升序排列，left 到 right-1 的所有位置与当前 right 组成的配对都能满足条件。计数器增加 right - left，然后将 right 左移一位。nums[left] + nums[right] <= nums[k]，说明两边之和太小，将 left 右移来增大和。#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 升序排序
int n = nums.size();
int ret = 0;
for (int i = n - 1; i >= 2; i--) { // 因为最少三条边，所以 i>=2
int left = 0, right = i - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]) {
ret += right - left;
right--;
} else {
left++;
}
}
}
return ret;
}
};
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
int ret = 0;
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;
}
};
int main() {
vector<int> nums1 = {4, 2, 3, 4};
cout << Solution().triangleNumber(nums1) << endl;
return 0;
}
// 和为 s 的两个数字
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left = 0;
int right = price.size() - 1;
while (left < right) {
if (price[left] + price[right] > target) {
right--;
} else if (price[left] + price[right] < target) {
left++;
} else {
return {price[left], price[right]};
}
}
return {-1, -1};
}
};
// 和为 s 的两个数字
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left = 0;
int right = price.size() - 1;
while (left < right) {
if (price[left] + price[right] > target) {
right--;
} else if (price[left] + price[right] < target) {
left++;
} else {
return {price[left], price[right]};
}
}
return {-1, -1};
}
};
int main() {
vector<int> nums1 = {3, 9, 12, 15};
vector<int> result = Solution().twoSum(nums1, 18);
cout << "[";
for (int i = 0; i < result.size(); i++) {
cout << result[i];
(i < result.() - ) {
cout << ;
}
}
cout << << endl;
;
}
本文通过「有效三角形个数」和「和为 s 的两个数字」两个经典问题，展示了双指针在数学组合问题中的精妙应用。核心思想在于排序预处理 + 指针智能移动。掌握这些基础模型后，可进一步挑战三数之和、四数之和等进阶问题，体会分治思想在算法设计中的威力。