day7: 剩下的两题：
- 15. 三数之和
- 18. 四数之和
15. 三数之和
题目链接
状态：
文档：programmercarl.com
注意：
这和第一题中的四数相加Ⅱ很像，如果用哈希算法的思路就是：
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 遍历数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。（i ≠ j ≠ k）
（哈希算法）思路：
首先创建一个二维数组，来存放符合条件的三元组。
因为要去重，不能出现像是：[-1,0,1] [0,1,-1]的情况，这样也算是重复。
所以要用一个 全局函数sort 进行排序，按照从小到大的顺序，就不会出现像上述一样的情况。
但是还要考虑一种去重：数组中有多个重复的元素。
这种去重就要通过剪枝来进行操作了。
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// 找出a + b + c = 0
// a = nums[i], b = nums[j], c = -(a + b)
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
//短路条件
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
//不可以让 nums[i] == nums[i+1] --> 这样会让后面的j=i+1 失去遍历一些值的机会
continue;
}
unordered_set<int> set; //set有自动去重的效果
//开始遍历第二个数
for (int j = i + 1; j < nums.size(); j++) {
if (j > i + 2
&& nums[j] == nums[j-1]
&& nums[j-1] == nums[j-2]) { // 三元组元素b去重
continue;
}
int c = 0 - (nums[i] + nums[j]);
if (set.find(c) != set.end()) {
result.push_back({nums[i], nums[j], c});
set.erase(c);// 三元组元素c去重
} else {
set.insert(nums[j]);
}
}
}
return result;
}
};
注意：
用哈希法的话去重会很麻烦，让人一下子想不到，所以选择用双指针的方式，来不断的寻找合适的值。
(双指针)思路：
拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//创建一个二维数组reslt 存放最后结果
vector<vector<int>> result;
//排序
sort(nums.begin(),nums.end());
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for(int i = 0;i<nums.size();i++)
{
//排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if(nums[i] > 0)
{
return result;
}
//对a进行去重
if(i>0 && nums[i] == nums[i-1])
{
//跳过这个重复的元素
continue;
}
//排除万难 开始遍历
int left = i+1;
int right = nums.size()-1;
while(right > left)
{
if(nums[i] + nums[left] + nums[right] > 0)
{
right--;
}
else if(nums[i] + nums[left] + nums[right] < 0)
{
left++;
}
else
{
//结果==0，放入result中
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
//进行b去重
while(right > left && nums[left] == nums[left+1])
{
left++;
}
//进行c去重
while(right > left && nums[right] == nums[right-1])
{
right--;
}
//找到答案后，双指针收缩
right--;
left++;
}
}
}
return result;
}
};
18. 四数之和
题目链接
状态：有一半思路，没做出来
文档：programmercarl.com
思路：
和上一题有些类似，都是使用双指针的方法，先找前两个数，在用双指针去遍历后两个数。
首先创建一个二维数组，存放最后的结果。
再对数组进行一个 全局函数sort 排序操作，进行第一步去重。
先找第一个数 k，先剪枝（一级剪枝：对a），也就是判断短路条件：都得是正数才行。
再对 k 进行去重操作（一级去重，对a）
然后再去找第二个数 i，i=k+1，先剪枝（二级剪枝：对b），和一级剪枝一样，都得是正数才行。
再对 i 进行去重操作（二级去重，对b）
有了前两个数的和了，开始创建双指针，一个是left = i+1，一个是right = nums.size()-1。
开始while循环遍历，此时的思路和三数之和这道题的思路是一样的：
四数之和>tar ==>> 数加多了，右指针左移。
四数之和<tar ==>> 数加少了，左指针右移。
四数之和=tar ==>> 存入二维数组中，此时要对left 和 right 进行去重操作，去重完毕之后，双指针收缩，继续下一轮。
最后返回二维数组。
代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//二维数组，存放结果
vector<vector<int>> result;
//对数组进行排序
sort(nums.begin(),nums.end());
//四个数 k i left right
for(int k = 0;k<nums.size();k++)
{
//一级剪枝：
//首先对k进行剪枝：有不符合的情况直接就return
//[-4 -1 0 5] tar=-5,so [-4 -1 0]就符合条件 但是-4 > target
//如果只判断这个条件的话 就会把正确的结果也剪掉了
//nums[k] > target && target > 0 && nums[k] > 0
//nums[k] > target && nums[k] >= 0
//都是正数才行 才能满足这个短路条件
if(nums[k] > target && target > 0 && nums[k] > 0 )
{
break;
}
//一级去重
//k去重 要判断k>0,因为有一个k-1的操作
if(k>0 && nums[k] == nums[k-1])
{
continue;
}
//遍历第二个数 i
for(int i = k+1;i<nums.size();i++)
{
//二级剪枝
//都得是正数才行
//nums[k]+nums[i] > target && target > 0 && nums[k] + nums[i] > 0
//nums[k]+nums[i] > target && nums[k] + nums[i] >= 0
if(nums[k]+nums[i] > target && target > 0 && nums[k] + nums[i] > 0)
{
break;
}
//二级去重
if(i>k+1 && nums[i] == nums[i-1])
{
continue;
}
//开始设置left right
int left = i+1;
int right = nums.size()-1;
while(right > left)
{
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if((long)nums[k] + nums[i] + nums[left] +nums[right] > target)
{
//说明加多了
right--;
}
else if((long)nums[k] + nums[i] + nums[left] +nums[right] < target)
{
//说明加少了
left++;
}
else{
//==target
result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});
//对left去重
while(right > left && nums[left] == nums[left+1])
{
left++;
}
//对right去重
while(right > left && nums[right] == nums[right-1])
{
right--;
}
//找到答案时，left、right指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
};
