双指针——三数之和模板
时间：2022-12-29 03:30:00
滑动窗-三数之和模板汇总题单：
LC15. 三数之和 https://leetcode.cn/problems/3sum/
LC16. 三数之和最接近 https://leetcode.cn/problems/3sum-closest/
LC259. 三数之和较小 https://leetcode.cn/problems/3sum-smaller/
LC18. 四数之和 https://leetcode.cn/problems/4sum/
LC1099. 小于 K 的两数之和 https://leetcode.cn/problems/two-sum-less-than-k/
LC1. 两数之和 https://leetcode.cn/problems/two-sum/
代码模板的三数之和
用三数之和做模板 知识点：数组排序,重复数字，双指针 class Solution {
public: vector<vector<int>> threeSum(vector<int>& nums, int target) {
int n = nums.size(); //先对数组进行排序 sort(nums.begin(), nums.end()); for (int i = 0; i < n; i ) {
///出现重复元素，去除元素 if (i > 0 && nums[i] == nums[i - 1]) continue; 左指针代表元素最小，右指针代表元素最大，向中间缩进 int j = i 1, k = n - 1; while (j < k) {
///防止数据溢出，使用long long定义数据类型 long long sum = 0LL nums[i] nums[j] nums[k];
if (sum == target)
{
//res.push_back({nums[i], nums[j], nums[k]});
res.push_back(vector<int>{
nums[i], nums[j], nums[k]});
//将符合答案要求的元素放入结果中，双指针开始移动。左指针右移，右指针左移
++j;
--k;
//左指针遇到重复元素，右移
while (j < k && nums[j] == nums[j - 1]) ++j;
//右指针遇到重复元素，左移。
while (j < k && nums[k] == nums[k + 1]) --k;
}
//当元素之和sum小于目标值时，左指针右边移;元素之后sum大于目标值时，右指针左移。
else if (sum < target) ++j;
else --k;
}
}
return res;
}
};
LC15. 三数之和 https://leetcode.cn/problems/3sum/
#双指针
LC 15 三数之和
知识点：数组排序,去重复的数字，双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++)
{
if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = n - 1;
while (j < k)
{
long long sum = 0LL + nums[i] + nums[j] + nums[k];
if (sum == 0)
{
//res.push_back({nums[i], nums[j], nums[k]});
res.push_back(vector<int>{
nums[i], nums[j], nums[k]});
++j;
--k;
while (j < k && nums[j] == nums[j - 1]) ++j;
while (j < k && nums[k] == nums[k + 1]) --k;
}
else if (sum < 0) ++j;
else --k;
}
}
return res;
}
};
LC16. 最接近的三数之和 https://leetcode.cn/problems/3sum-closest/
#双指针
LC 16 最接近的三数之和
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end()); //数组排序，从小到大
int res = nums[0] + nums[1] + nums[2]; //初始化最开始的三数之和
for (int i = 0; i < n; i++)
{
if (i > 0 && nums[i] == nums[i - 1]) continue; //遇到重复的值跳过
int j = i + 1, k = n - 1; //双指针，滑动窗口开始收缩
while (j < k)
{
int sum = nums[i] + nums[j] + nums[k];
//判断最开始的三数之和res与滑动窗口中的三数之和sum进行与目标值比较，更新res。
if (abs(sum - target) < abs(res - target)) res = sum;
else if (sum > target) --k; //while (j < k && nums[k] == nums[k + 1]) --k; 可加可不加
else if (sum < target) ++j; //while (j < k && nums[j] == nums[j - 1]) ++j; 可加可不加
else if (sum == target) return res;
}
}
return res;
}
};
LC259. 较小的三数之和 https://leetcode.cn/problems/3sum-smaller/
#双指针
LC 259 较小的三数之和
知识点：数组排序，双指针
class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
int cnt = 0;
for (int i = 0; i < n - 2; i++)
{
int j = i + 1, k = n - 1;
while (j < k)
{
int sum = nums[i] + nums[j] + nums[k];
if (sum < target)
{
cnt += k - j;
++j;
}
else
{
--k;
}
}
}
return cnt;
}
};
LC18. 四数之和 https://leetcode.cn/problems/4sum/
#双指针
LC 18 四数之和
知识点:同三数之和
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> res;
if (n < 4) return res;
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 3; i++)
{
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++)
{
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = n - 1;
while (k < l)
{
long long sum = 0LL+ nums[i] + nums[j] + nums[k] + nums[l];
if (sum == target)
{
res.push_back({
nums[i], nums[j], nums[k], nums[l]});
++k;
--l;
while (k < l && nums[k] == nums[k - 1]) ++k;
while (k < l && nums[l] == nums[l + 1]) --l;
}
else if (sum > target)
{
--l;
}
else if (sum < target)
{
++k;
}
}
}
}
return res;
}
};
LC1099. 小于 K 的两数之和 https://leetcode.cn/problems/two-sum-less-than-k/
#双指针
LC 1099 小于K的两数之和
知识点:
class Solution {
public:
int twoSumLessThanK(vector<int>& nums, int k) {
int n = nums.size(), res = -1;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (nums[i] + nums[j] < k)
{
res = max(res, nums[i] + nums[j]);
}
}
}
return res;
}
};
LC1. 两数之和 https://leetcode.cn/problems/two-sum/
LC 1。两数之和
知识点:哈希表
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
int n = nums.size();
for (int i = 0; i < n; i++)
{
map[nums[i]] = i;
}
for (int i = 0; i < n; i++)
{
//map[target - nums[i]] != i 防止目标值是当前值的nums[i]的两倍
if (map.count(target - nums[i]) && map[target - nums[i]] != i)
{
return {
i, map[target - nums[i]]};
}
}
return {
};
}
};
或者一遍哈希表
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
int n = nums.size();
for (int i = 0; i < n; i++)
{
if (map.count(target - nums[i]))
{
return {
i, map[target - nums[i]]};
}
map[nums[i]] = i;
}
return {
};
}
};
