【优选算法】（第四篇）
目录
三数之和（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个整数数组nums，判断是否存在三元组[nums[i],nums[j],nums[k]]满⾜i!=j、i!=k且j!=k，同时还满⾜nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。
注意：答案中不可以包含重复的三元组。
⽰例1：输⼊：nums=[-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]
解释：nums[0]+nums[1]+nums[2]=(-1)+0+1=0。nums[1]+nums[2]+nums[4]=0+1+(-1)=0。nums[0]+nums[3]+nums[4]=(-1)+2+(-1)=0。不同的三元组是[-1,0,1]和[-1,-1,2]。
注意，输出的顺序和三元组的顺序并不重要。
⽰例2：输⼊：nums=[0,1,1]输出：[]
解释：唯⼀可能的三元组和不为0。
⽰例3：输⼊：nums=[0,0,0]输出：[[0,0,0]]
解释：唯⼀可能的三元组和为0。
提⽰：3<=nums.length<=3000-10^5<=nums[i]<=10^5
讲解算法原理
解法（排序+双指针）：算法思路：
本题与两数之和类似，是⾮常经典的⾯试题。
与两数之和稍微不同的是，题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和那⾥⽤的双指针思想，来对我们的暴⼒枚举做优化：
i. 先排序；
ii. 然后固定⼀个数 a ：
iii. 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意的是，这道题⾥⾯需要有「去重」操作~
i. 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
ii. 当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素
编写代码
c++算法代码；
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> ret;
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利⽤双指针解决问题
int n = nums.size();
for(int i = 0; i < n; ) // 固定数 a
{
if(nums[i] > 0) break; // ⼩优化
int left = i + 1, right = n - 1, target = -nums[i];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else
{
ret.push_back({nums[i], nums[left], nums[right]});
left++, right--;
// 去重操作 left 和 right
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1])
right--;
}
}
// 去重 i
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};java算法代码：
class Solution
{
public List<List<Integer>> threeSum(int[] nums)
{
List<List<Integer>> ret = new ArrayList<>();
// 1. 排序
Arrays.sort(nums);
// 2. 利⽤双指针解决问题
int n = nums.length;
for(int i = 0; i < n; ) // 固定数 a
{
if(nums[i] > 0) break; // ⼩优化
int left = i + 1, right = n - 1, target = -nums[i];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else
{
// nums[i] nums[left] num[right]
ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],
nums[left], nums[right])));
left++; right--; // 缩⼩区间继续寻找
// 去重：left right
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1])
right--;
}
}
// 去重：i
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
}四数之和（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个由n个整数组成的数组nums，和⼀个⽬标值target。请你找出并返回满⾜下述全部条件且不重复的四元组[nums[a],nums[b],nums[c],nums[d]]（若两个四元组元素⼀⼀对应，则认为两个四元组重复）：
◦ 0<=a,b,c,d<n
◦ a、b、c和d互不相同
◦ nums[a]+nums[b]+nums[c]+nums[d]==target
你可以按任意顺序返回答案。
⽰例1：
输⼊：nums=[1,0,-1,0,-2,2],target=0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
⽰例2：
输⼊：nums=[2,2,2,2,2],target=8
输出：[[2,2,2,2]]
提⽰：
1<=nums.length<=200
-109<=nums[i]<=109
-109<=target<=109
讲解算法原理
解法（排序+双指针）
算法思路：
a. 依次固定⼀个数 a ；
b. 在这个数 a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于 target
- a 即可。
编写代码
c++算法代码：
class Solution
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利⽤双指针解决问题
int n = nums.size();
for(int i = 0; i < n; ) // 固定数 a
{
// 利⽤ 三数之和
for(int j = i + 1; j < n; ) // 固定数 b
{
// 双指针
int left = j + 1, right = n - 1;
long long aim = (long long)target - nums[i] - nums[j];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum < aim) left++;
else if(sum > aim) right--;
else
{
ret.push_back({nums[i], nums[j], nums[left++],
nums[right--]});
// 去重⼀
while(left < right && nums[left] == nums[left - 1])
left++;
while(left < right && nums[right] == nums[right + 1])
right--;
}
}
// 去重⼆
j++;
while(j < n && nums[j] == nums[j - 1]) j++;
}
// 去重三
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};java算法代码实现：
class Solution
{
public List<List<Integer>> fourSum(int[] nums, int target)
{
List<List<Integer>> ret = new ArrayList<>();
// 1. 排序
Arrays.sort(nums);
// 2. 利⽤双指针解决问题
int n = nums.length;
for(int i = 0; i < n; ) // 固定数 a
{
// 三数之和
for(int j = i + 1; j < n; ) // 固定数 b
{
// 双指针
int left = j + 1, right = n - 1;
long aim = (long)target - nums[i] - nums[j];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > aim) right--;
else if(sum < aim) left++;
else
{
ret.add(Arrays.asList(nums[i], nums[j], nums[left++],
nums[right--]));
// 去重⼀
while(left < right && nums[left] == nums[left - 1])
left++;
while(left < right && nums[right] == nums[right + 1])
right--;
}
}
// 去重⼆
j++;
while(j < n && nums[j] == nums[j - 1]) j++;
}
// 去重三
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
}原文地址：https://blog.csdn.net/weixin_73861555/article/details/142558591
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！