分析
-
本题的考点:双指针。
-
这一题和Leetcode 0015 三数之和的解法一样,只不过需要枚举两个元素,另外两个元素使用双指针寻找。
代码
- C++
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int i = 0; i < nums.size(); i++) {
if (i && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size(); j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// 双指针算法
for (int k = j + 1, u = nums.size() - 1; k < u; k++) {
if (k > j + 1 && nums[k] == nums[k - 1]) continue;
while (k < u - 1 && nums[i] + nums[j] + nums[k] + nums[u - 1] >= target) u--;
if (nums[i] + nums[j] + nums[k] + nums[u] == target) {
res.push_back({nums[i], nums[j], nums[k], nums[u]});
}
}
}
}
return res;
}
};
- Java
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
for (int k = j + 1, u = nums.length - 1; k < u; k++) {
if (k > j + 1 && nums[k] == nums[k - 1]) continue;
while (k < u - 1 && nums[i] + nums[j] + nums[k] + nums[u - 1] >= target) u--;
if (nums[i] + nums[j] + nums[k] + nums[u] == target) {
res.add(get(nums[i], nums[j], nums[k], nums[u]));
}
}
}
}
return res;
}
private List<Integer> get(int a, int b, int c, int d) {
List<Integer> res = new ArrayList<>();
res.add(a); res.add(b); res.add(c); res.add(d);
return res;
}
}
时空复杂度分析
-
时间复杂度:$O(n^3)$。两重循环+双指针。
-
空间复杂度:$O(1)$。