leetcode 18. 四数之和
题目详情
题目链接 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 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] ]
我的代码
class Solution {
public:
vector
<vector
<int>> fourSum(vector
<int>& nums
, int target
) {
sort(nums
.begin(), nums
.end());
vector
<vector
<int>> results
;
vector
<int> result
;
int n
= nums
.size();
for (int i
= 0; i
< n
; ++i
) {
if (i
> 0 && nums
[i
] == nums
[i
- 1]) {
continue;
}
for (int j
= i
+ 1; j
< n
; ++j
) {
if (j
> i
+ 1 && nums
[j
] == nums
[j
- 1]) {
continue;
}
int target1
= target
- (nums
[i
] + nums
[j
]);
int left
= j
+ 1, right
= n
- 1;
while (left
< right
) {
int sum
= nums
[left
] + nums
[right
];
if (sum
== target1
) {
results
.push_back({nums
[i
], nums
[j
], nums
[left
], nums
[right
]});
++left
, --right
;
while (left
<= right
&& nums
[left
] == nums
[left
- 1]) {
++left
;
}
while(left
<= right
&& nums
[right
] == nums
[right
+ 1]) {
--right
;
}
} else if (sum
< target1
) {
++left
;
while (left
<= right
&& nums
[left
] == nums
[left
- 1]) {
++left
;
}
} else {
--right
;
while(left
<= right
&& nums
[right
] == nums
[right
+ 1]) {
--right
;
}
}
}
}
}
return results
;
}
};
我的成绩
执行结果：通过 执行用时：92 ms, 在所有 C++ 提交中击败了59.37%的用户 内存消耗：12.7 MB, 在所有 C++ 提交中击败了5.01%的用户
一些想法
先固定两点，然后使用双指针法。
执行用时为 4 ms 的范例
class Solution {
public:
vector
<vector
<int>> fourSum(vector
<int>& nums
, int target
) {
vector
<vector
<int>> res
;
int nSize
= nums
.size();
if(nSize
<4)
{
return res
;
}
sort(nums
.begin(), nums
.end());
int low1
,low2
,l
,r
;
for(low1
= 0; low1
< nSize
- 3; low1
++)
{
int min1
= nums
[low1
]+nums
[low1
+1]+nums
[low1
+2]+nums
[low1
+3];
if(min1
> target
)
{
break;
}
int max1
= nums
[low1
]+nums
[nSize
-3]+nums
[nSize
-2]+nums
[nSize
-1];
if(max1
< target
)
{
continue;
}
for(low2
= low1
+1; low2
< nSize
- 2; low2
++)
{
int min2
= nums
[low1
]+nums
[low2
]+nums
[low2
+1]+nums
[low2
+2];
if(min2
> target
)
{
break;
}
int max2
= nums
[low1
]+nums
[low2
]+nums
[nSize
-2]+nums
[nSize
-1];
if(max2
< target
)
{
continue;
}
l
= low2
+1;
r
= nSize
-1;
while(l
< r
)
{
int sum
= nums
[low1
]+nums
[low2
]+nums
[l
]+nums
[r
];
if(sum
== target
)
{
vector
<int> temp
;
temp
.push_back(nums
[low1
]);
temp
.push_back(nums
[low2
]);
temp
.push_back(nums
[l
]);
temp
.push_back(nums
[r
]);
res
.push_back(temp
);
while(l
<r
&& nums
[l
] == nums
[++l
]);
while(l
<r
&& nums
[r
] == nums
[--r
]);
}
else if(sum
< target
)
{
l
++;
}
else
{
r
--;
}
}
while(nums
[low2
] == nums
[low2
+1] && low2
+1 < nSize
-2)
{
low2
++;
}
}
while(nums
[low1
] == nums
[low1
+1] && low1
+1 < nSize
-3)
{
low1
++;
}
}
return res
;
}
};
思考
参见官方解答
