四数之和 - 力扣中等
admin
2024-03-16 01:07:53
0

题目链接

四数之和

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

0 <= a, b, c, d < n
a、b、cd 互不相同
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<=1091 <= nums.length <= 200 \\ -10^9 <= nums[i] <= 10^9 \\ -10^9 <= target <= 10^9 \\ 1<=nums.length<=200−109<=nums[i]<=109−109<=target<=109

解题思路

思路一

双指针,时间复杂度为O(N3)O(N^3)O(N3)
排序
枚举前两个数字,剩下两个使用双指针lr枚举。

  • 如果nums[l] + nums[r] == target - nums[i] - nums[j],找到答案,更新lr
  • 如果nums[l] + nums[r] > target - nums[i] - nums[j],找到答案,r左移。
  • 如果nums[l] + nums[r] < target - nums[i] - nums[j],找到答案,l右移。

思路二

二分查找,时间复杂度为O(N3logN)O(N^3logN)O(N3logN)
排序
枚举前三个数字,查找第四个数target - nums[i] - nums[j] - nums[k]是否在数组里面。
很不幸,跑到最后一个测试用例超时。

注意溢出!

解题代码

思路一

#include
#include
#include
#include
using namespace std;class Solution {public:vector>ans;map>>vis;vector> fourSum(vector& nums, int target) {sort(nums.begin(),nums.end());for(int i=0;ifor(int j=i+1;jint l=j+1;int r=nums.size()-1;long long tmp_target = (long long)target-nums[i]-nums[j];while(lif(l==i||l==j){l++;continue;}if(r==i||r==j){r--;continue;}long long lr_sum = (long long)nums[l]+nums[r];if(lr_sum==tmp_target){if(vis[nums[i]][nums[j]][nums[l]]==0){vis[nums[i]][nums[j]][nums[l]]=1;vectorpath = {nums[i],nums[j],nums[l],nums[r]};ans.push_back(path);}l++;r--;continue;}if(lr_suml++;continue;}if(lr_sum>tmp_target){r--;continue;}}}}//        for(int i=0;i
//            vectorpath=ans[i];
//            for(int p=0;p
//                cout<//-2,-1,0,0,1,2vectornums = {0,0,0,0};int target = 1;Solution so = Solution();so.fourSum(nums,target);return 0;
}

思路二 (超时)

最后一个测试用例超时

#include
#include
#include
#include
using namespace std;class Solution {
public:vector>ans;map>>vis;int binary_search(vector&nums, int sidx, int target){int l=sidx;int r=nums.size()-1;while(lint m = (l+r)>>1;if(nums[m]==target)return m;if(nums[m]> fourSum(vector& nums, int target) {sort(nums.begin(),nums.end());for(int i=0;ifor(int j=i+1;jfor(int k=j+1;kif(vis[nums[i]][nums[j]][nums[k]])continue;long long d = (long long)target-nums[i]-nums[j]-nums[k];if(dnums[nums.size()-1])continue;int idx = binary_search(nums,k+1,d);if(idx!=-1){vis[nums[i]][nums[j]][nums[k]]=1;// vectorpath = {nums[i],nums[j],nums[k],nums[idx]};ans.push_back({nums[i],nums[j],nums[k],nums[idx]});
//                        for(int p=0;p
//                            cout<//-2,-1,0,0,1,2vectornums = {0,0,0,0};int target = 1;Solution so = Solution();so.fourSum(nums,target);return 0;
}

相关内容

热门资讯

怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...
安卓系统手写%怎样调出,具体实... 你有没有遇到过这种情况:在使用安卓手机的时候,突然想用手写输入法来记录一些灵感或者重要信息,可是怎么...
安卓手机重置 系统设置,轻松恢... 手机用久了是不是感觉卡顿得厉害?别急,今天就来教你怎么给安卓手机来个大变身——重置系统设置!想象你的...
win如何安装安卓系统,Win... 哇,你有没有想过,让你的Win系统也能玩转安卓应用?没错,就是那种在手机上轻松自如的安卓系统,现在也...
苹果qq和安卓系统,跨平台体验... 你有没有发现,现在手机市场上,苹果和安卓的较量可是越来越激烈了呢!咱们就来聊聊这个话题,看看苹果QQ...
显示最好的安卓系统,探索最新旗... 你有没有想过,为什么安卓系统那么受欢迎呢?它就像一个魔法盒子,里面装满了各种神奇的魔法。今天,就让我...
安卓app怎么降级系统,系统版... 你有没有发现,有时候安卓手机的系统更新后,新功能虽然炫酷,但老系统用起来更顺手呢?别急,今天就来教你...
雷军脱离安卓系统,引领科技变革... 你知道吗?最近科技圈可是炸开了锅,因为我们的雷军大大竟然宣布要脱离安卓系统,这可真是让人大跌眼镜啊!...
安卓系统自动开网络,安卓系统自... 你有没有发现,手机里的安卓系统有时候会自动开启网络连接,这可真是让人又爱又恨啊!有时候,你正专心致志...
安卓系统怎样控制后台,因为服务... 手机里的安卓系统是不是感觉越来越卡了?后台程序太多,不仅耗电还影响性能。别急,今天就来教你怎么巧妙地...
安卓系统打游戏推荐,一触即达! 你有没有发现,现在手机游戏越来越好玩了?不管是休闲小游戏还是大型MMORPG,都能在手机上畅玩。但是...