网站开发小程序开发公司,潍坊建设网站的公司电话,北京app开发哪家好,做网站工作好么题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target#xff0c;判断 nums 中是否存在四个元素 a#xff0c;b#xff0c;c 和 d #xff0c;使得 a b c d 的值与 target 相等#xff1f;找出所有满足条件且不重复的四元组。
注意#xff1a;答案中不可以包…题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target判断 nums 中是否存在四个元素 abc 和 d 使得 a b c d 的值与 target 相等找出所有满足条件且不重复的四元组。
注意答案中不可以包含重复的四元组。 示例 给定数组 nums [1, 0, -1, 0, -2, 2]和 target 0。 满足要求的四元组集合为 [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] 思路
四数之和和代码随想录阅读笔记-哈希表【三数之和】-CSDN博客是一个思路都是使用双指针法, 基本解法就是在代码随想录阅读笔记-哈希表【三数之和】-CSDN博客的基础上再套一层for循环。但是有一些细节需要注意例如 不要判断nums[k] target 就返回了三数之和 可以通过 nums[i] 0 就返回了因为 0 已经是确定的数了四数之和这道题目 target是任意值。比如数组是[-4, -3, -2, -1]target是-10不能因为-4 -10而跳过。但是我们依旧可以去做剪枝逻辑变成nums[i] target (nums[i] 0 || target 0)就可以了。
代码随想录阅读笔记-哈希表【三数之和】-CSDN博客的双指针解法是一层for循环num[i]为确定值然后循环内有left和right下标作为双指针找到nums[i] nums[left] nums[right] 0。
四数之和的双指针解法是两层for循环nums[k] nums[i]为确定值依然是循环内有left和right下标作为双指针找出nums[k] nums[i] nums[left] nums[right] target的情况三数之和的时间复杂度是O(n^2)四数之和的时间复杂度是O(n^3) 。那么一样的道理五数之和、六数之和等等都采用这种解法。
对于代码随想录阅读笔记-哈希表【三数之和】-CSDN博客双指针法就是将原本暴力O(n^3)的解法降为O(n^2)的解法四数之和的双指针解法就是将原本暴力O(n^4)的解法降为O(n^3)的解法。
之前博客的经典题目代码随想录阅读笔记-哈希表【四数相加II】-CSDN博客相对于本题简单很多因为本题是要求在一个集合中找出四个数相加等于target同时四元组不能重复。而代码随想录阅读笔记-哈希表【四数相加II】-CSDN博客是四个独立的数组只要找到A[i] B[j] C[k] D[l] 0就可以不用考虑有重复的四个元素相加等于0的情况所以相对于本题还是简单了不少。
我们来回顾一下几道题目使用了双指针法。
双指针法将时间复杂度O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级除了本题还有之前写过的题目如下
代码随想录阅读笔记-数组【移除元素】-CSDN博客代码随想录阅读笔记-哈希表【三数之和】-CSDN博客
链表相关双指针题目
代码随想录阅读笔记-链表【反转链表】-CSDN博客代码随想录阅读笔记-链表【删除链表倒数第n节点】-CSDN博客代码随想录阅读笔记-链表【链表相交】-CSDN博客代码随想录阅读笔记-链表【环形链表II】-CSDN博客
双指针法在字符串题目中还有很多应用后面还会介绍到。
C代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint result;sort(nums.begin(), nums.end());for (int k 0; k nums.size(); k) {// 剪枝处理if (nums[k] target nums[k] 0) {break; // 这里使用break统一通过最后的return返回}// 对nums[k]去重if (k 0 nums[k] nums[k - 1]) {continue;}for (int i k 1; i nums.size(); i) {// 2级剪枝处理if (nums[k] nums[i] target nums[k] nums[i] 0) {break;}// 对nums[i]去重if (i k 1 nums[i] nums[i - 1]) {continue;}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--;// nums[k] nums[i] nums[left] nums[right] target 会溢出} else if ((long) nums[k] nums[i] nums[left] nums[right] target) {left;} else {result.push_back(vectorint{nums[k], nums[i], nums[left], nums[right]});// 对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 result;}
}; 时间复杂度: O(n^3)空间复杂度: O(1) 优化二级剪枝的部分
if (nums[k] nums[i] target nums[k] nums[i] 0) {break;
}可以优化为
if (nums[k] nums[i] target nums[i] 0) {break;
}因为只要 nums[k] nums[i] target那么想要符合题意的唯一条件就是此时nums[k] 和 nums[i]都为负数所以需要nums[i]后面还有负数才能使和变小进而去接近target那么 nums[i] 后面的数都是正数的话就一定 不符合条件了。
