leetcode18--四数之和

2024-03-14 18:28
文章标签 四数 leetcode18

本文主要是介绍leetcode18--四数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 题意

求所有数组中四个数之和为指定值的所有组合

四数之和

2. 题解

暴力没想到也能过

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {std::sort(nums.begin(), nums.end());vector<vector<int>> ans;int sz = nums.size();for (int i = 0;i < sz; ++i) {if (i > 0 && nums[i] == nums[i - 1])continue;for (int j = i + 1;j < sz; ++j) {if (j > i + 1 && nums[j] == nums[j - 1])continue;int lp = j + 1;int rp = sz - 1;long long tot = (long long) nums[i] + nums[j];while (lp < rp) {long long rest = nums[lp] + nums[rp];if ( tot + rest == target) {ans.push_back({nums[i],nums[j],nums[lp],nums[rp]});++lp;--rp;while (lp< rp && nums[lp] == nums[lp-1]) {++lp;}while (lp < rp && nums[rp] == nums[rp+1]){--rp;}}else if (tot + rest  < target) {lp++;}else {rp--;}}}}return ans;}
};

双指针: 注意处理相等时的情况,需要左右指针都移到与上一位置不同的地方。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {std::sort(nums.begin(), nums.end());vector<vector<int>> ans;int sz = nums.size();for (int i = 0;i < sz; ++i) {if (i > 0 && nums[i] == nums[i - 1])continue;for (int j = i + 1;j < sz; ++j) {if (j > i + 1 && nums[j] == nums[j - 1])continue;int lp = j + 1;int rp = sz - 1;long long tot = (long long) nums[i] + nums[j];while (lp < rp) {long long rest = nums[lp] + nums[rp];if ( tot + rest == target) {ans.push_back({nums[i],nums[j],nums[lp],nums[rp]});++lp;--rp;while (lp< rp && nums[lp] == nums[lp-1]) {++lp;}while (lp < rp && nums[rp] == nums[rp+1]){--rp;}}else if (tot + rest  < target) {lp++;}else {rp--;}}}}return ans;}
};

这篇关于leetcode18--四数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/809316

相关文章

第十八题:四数之和

题目描述 给定一个包含 n 个整数的数组 nums 和一个目标值 target,找出 nums 中的四个整数,使得它们的和等于 target。你可以假设每个输入都只有一个解决方案,并且不能使用同一个元素多次。 实现思路 采用排序加双指针的方法来解决这个问题。首先对数组进行排序,然后遍历数组,对于每一个元素,设定一个新的目标值为原目标值减去这个元素的值,再利用三数之和的解法找到剩下的三个数。为

★ 算法OJ题 ★ 力扣18 - 四数之和

Ciallo~(∠・ω< )⌒☆ ~ 今天,爱丽速子将和大家一起做一道双指针算法题--四数之和~ 目录 一  题目 二  算法解析 三  编写算法  做此题前最好先看一下前两篇博客~: ★ 算法OJ题 ★ 力扣 LCR179 - 和为 s 的两个数字-CSDN博客 ★ 算法OJ题 ★ 力扣15 - 三数之和-CSDN博客 一  题目 18. 四数之和 - 力扣(Lee

算法------四数相加 II (java 版本)

题目: 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果不会超过 2^31 - 1 。例如:输入:A = [

代码随想录 -- 哈希表 -- 四数之和

18. 四数之和 - 力扣(LeetCode) 思路:(与三数之和类似,在外面加一层循环)         1. 先将 nums 按升序排序         2. 初始状态:k = 0,i = k+1,left = i+1,right = len(nums)-1         3. 进入第一层 for 循环:         如果 nums[k]>0 and target>0 and

Leetcode18: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element al

学习记录:js算法(十六):四数之和

文章目录 四数之和我的思路 总结 四数之和 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。 请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复): 0 <= a, b, c, d < na、b、c 和 d 互不相同nums[a]

Leetcode 18-四数之和

题解看代码随想录 /* 1.先排序,为了便于使用双指针,复杂度O(logN) 2.固定最小指针a,b,双指针c和d分别从0和len-1向中间移动 从两端向中间移动是为了使得两个数下标不重合,且可以将时间复杂度从双重循环的O(N4)降到O(N3) 3.终止条件:a>N-3||nums[a]>0(此时四数之和必定大于0) 3.不可以包含重复元素:前后元素相同时跳过 */ class Solution

代码随想录算法训练营第六天|454.四数相加II;383. 赎金信;15. 三数之和;18. 四数之和

今日任务 ●  454.四数相加II ●  383. 赎金信 ●  15. 三数之和 ●  18. 四数之和 详细布置 454.四数相加II 建议:本题是 使用map 巧妙解决的问题,好好体会一下 哈希法 如何提高程序执行效率,降低时间复杂度,当然使用哈希法 会提高空间复杂度,但一般来说我们都是舍空间 换时间, 工业开发也是这样。 题目链接:. - 力扣(LeetCode) 题目链接/文

算法008:四数之合

四数之和. - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/4sum/description/ 在前面的两个题中,我们已经完成了两数之和和三数之和,到本题四数之和,其实也只是前几个题的延伸,在三数之和的基础上再固定一个数字。 先固定一个数字,剩下三个数按照三数之和的方

day07--454.四数相加II+383. 赎金信+ 15. 三数之和+ 18. 四数之和

一、454.四数相加II 题目链接:https://leetcode.cn/problems/4sum-ii/ 文章讲解:https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE 视频讲解:https://www