题目链接

四数之和

给你一个由 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

思路二 (超时)

最后一个测试用例超时

#include
#include
#include
#include