广州网站制作设计公司,保定网站建设电话,谢馥春网站建设的优势,搜狗网站录入代码随想录二刷 #xff5c;哈希表 #xff5c;四数之和 题目描述解题思路 代码实现 题目描述
18.四数之和
给你一个由 n 个整数组成的数组 nums #xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nu… 代码随想录二刷 哈希表 四数之和 题目描述解题思路 代码实现 题目描述
18.四数之和
给你一个由 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
解题思路 代码实现
与三数之和相同这道题是一样的做法直接使用双指针即可只需要在三数之和的基础上再加一层for循环找第四个数即可。
但有一个需要注意的点那就是因为三数之和中0是一个确定的数而四数之和中的target却不确定。
不要判断nums[k] target就返回了三数之和可以通过 nums[i] 0 就返回了因为 0 已经是确定的数了四数之和这道题目 target是任意值。比如数组是[-4, -3, -2, -1]target -10不能因为-4 -10而跳过。
但是我们依旧可以去做剪枝逻辑变成nums[i] target (nums[i] 0 || target 0)就可以了。
三数之和的双指针是一层for循环nums[i]为确定值然后通过left和right两个指针找到nums[i] nums[left] nums[right 0;
而四数之和的双指针是两层for循环确定nums[i] nums[j]通过left和right两个双指针找到nums[k] nums[i] nums[left] nums[right] target
class Solution {
public:vectorvectorint fourSum(vecetorint nums, int target) {vectorvectorint result;sort(nums.begin(), nums.end());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; i nums.size(); i) {if (nums[i] nums[j] target nums[i] nums[j] 0) break;if (j i 1 nums[j] nums[j - 1]) continue;int left j 1;int right nums.size() - 1;while (right left) {// nums[i] nums[j] nums[left] nums[right] target会溢出if ((long)nums[i] nums[j] nums[left] nums[right] target) right--;else if ((long)nums[i] nums[j] nums[left] nums[right] target) left;else {result.push_back(vectorint(nums[i], nums[j], nums[left], nums[right]));while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;right--;left;}}}}return reuslt;}
};
