LeetCode目标和问题总结
目标和,n个数和为m
https://www.jianshu.com/p/d32d3800e739
典型的dfs问题。
1.两数之和
想到的思路:
1)暴力枚举
2)排序后,双指针。分别在开头和结尾向中间遍历。
没有想到的思路:
3)hash 思路,遍历一次即可。示例代码使用的是unordered_map
遍历到x,如果target-x在hash表中出现过,返回target-x的坐标,两个坐标即为结果。如果没有出现过,则把x加入到hash表中。
相似
15.三数之和
已写博客:https://www.jianshu.com/p/7f14788ab788
题目
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = []
输出:[]
示例 3:
输入:nums = [0]
输出:[]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
和为0且不重复。难点是不重复.
去重的难点:
- 按照顺序枚举
「不重复」的本质是什么?我们保持三重循环的大框架不变,只需要保证:
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素;
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
2)对于每一重循环而言,相邻两次枚举的元素不能相同,否则也会造成重复。【在一次循环里,一个位置的元素不能重复出现两次】举个例子,如果排完序的数组为
[0, 1, 2, 2, 2, 3]
^ ^ ^
我们使用三重循环枚举到的第一个三元组为 (0, 1, 2)(0,1,2),如果第三重循环继续枚举下一个元素,那么仍然是三元组 (0, 1, 2)(0,1,2),产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素,即数组中的最后一个元素 33,枚举三元组 (0, 1, 3)(0,1,3)。
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
//分为三层循环,因为三个数之和。
//第一层,确定一个数
//第二层,两个指针,左指针通过遍历实现,右指针每次倒着找确定的那个数。
//因为去重,所以每个位置不需要遍历第二个相同的数字,一二层循环去重,右指针因为位置元素值确定,因此不用特别写去重
可以用 双指针去改进。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//分为三层
//第一层,确定一个数
//第二层,两个指针,左指针通过遍历实现,右指针每次倒着找确定的那个数。
//因为去重,所以每个位置不需要遍历第二个相同的数字,一二层循环去重,右指针因为位置元素值确定,因此不用特别写去重
sort(nums.begin(),nums.end());
vector<vector<int>> res;
for(int i=0;i<nums.size();i++){
if(i>0 && nums[i]==nums[i-1])//第一个位置不是相同的数
continue;
int left=i+1;
int right = nums.size()-1;
int red = -nums[i];
if(left==right){
break;
}
if(nums[i]>0){
break;
}
for(;left<right;left++){
if(left>i+1&&nums[left]==nums[left-1])//第二个位置不是相同的数
continue;
while(nums[left]+nums[right]>red&&right>left)
right-=1;
if(left==right)
break;
if(nums[left]+nums[right]==red){ //相等了
vector<int> now={nums[i],nums[right],nums[left]};
res.push_back(now);
right = nums.size()-1;
// right-=1;//判断不等于之前的
continue;
}
}
}
return res;
}
};
16.最接近的三数之和
已写博客:https://www.jianshu.com/p/b35092672bf6
可以直接暴力,
无需去重,其实思路比三数之和还好想一点。
18.四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + 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 = [], target = 0
输出:[]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//先排序
//循环两遍,确定 三四个数
//i从0开始,下一层从i+1,然后设置j=(i+1)+1 双指针
sort(nums.begin(),nums.end());
vector<vector<int>> res;
if(nums.size()<4)
return res;
for(int i=0;i<nums.size();i++){//第一重循环
if(nums[i]>target && nums[i]>0)//开始想剪枝,但是负值+负值会更小
break;
if(i>0 && nums[i]==nums[i-1])//去重
continue;
for(int j=i+1;j<nums.size();j++){ //第二重循环
if(nums[j]>target-nums[i] && nums[j]>0)
break;
if(j>i+1 && nums[j]==nums[j-1])
continue;
int red = target-nums[i]-nums[j];
//left,right 类似快排一样遍历
int index = -1;
int left = j+1;
int right = nums.size()-1;
// cout<<left<<right<<endl;
while(left<right){
if (nums[left] + nums[right] > red) {
right--;
} else if (nums[left] + nums[right]<red) {
left++;
} else {
vector<int> tmp={nums[i], nums[j], nums[left], nums[right]};
res.push_back(tmp);
// 找到答案时,双指针同时收缩
right--;
left++;
// 去重逻辑应该放在找到一个四元组之后
while (right > left && nums[right] == nums[right + 1]) right--;
while (right > left && nums[left] == nums[left - 1]) left++;
}
}
}
}
return res;
}
};
网友评论