四数之和 - 力扣中等

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、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<=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)
排序
枚举前两个数字，剩下两个使用双指针l和r枚举。

如果nums[l] + nums[r] == target - nums[i] - nums[j]，找到答案，更新l和r。
如果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;
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：TypeScript24(TS进阶用法ProxyReflect)

下一篇：计算机毕业设计Java进出货管理系统(源码+系统+mysql数据库+lw文档)

四数之和 - 力扣中等

四数之和

解题思路

思路一

思路二

解题代码

思路一

思路二 (超时)

相关内容

热门资讯