题目来源:. - 力扣(LeetCode)
题目思路分析
题目要求在给定的整数数组 nums
和一个目标值 target
中,找出所有独特的四元组(四个数),使得这四个数的和等于 target
。需要注意的是,解集中的数字不能重复。
为了解决这个问题,我们可以采用一种优化的四数之和算法。具体思路如下:
- 排序:首先对数组进行排序,这有助于我们跳过重复的数字,并且可以使用双指针技术来减少时间复杂度。
- 固定前两个数:通过两层循环分别固定前两个数(记为
nums[a]
和nums[b]
),其中a
从 0 遍历到n-4
(确保至少还有三个数可以选择),b
从a+1
遍历到n-3
。 - 跳过重复数字:在每层循环的开始,检查当前数字是否与上一个数字相同,如果是,则跳过,以避免重复的四元组。
- 提前终止:在固定
nums[a]
和nums[b]
后,可以通过检查当前四个数的最小和与最大和是否满足目标值target
来提前终止循环,从而减少不必要的计算。- 如果当前四个数的最小和(即
nums[a] + nums[a+1] + nums[a+2] + nums[a+3]
)大于target
,则无需继续遍历b
及其后的数,因为后面的和会更大。 - 如果当前四个数的最大和(即
nums[a] + nums[b] + nums[n-2] + nums[n-1]
,注意这里b
还未固定到最大值)小于target
,则可以跳过当前的a
,直接检查下一个a
,因为即使b
取最大值,和仍然小于target
。
- 如果当前四个数的最小和(即
- 双指针寻找后两个数:对于固定的
nums[a]
和nums[b]
,使用双指针c
和d
分别从b+1
和数组末尾开始,向中间移动,寻找满足nums[a] + nums[b] + nums[c] + nums[d] == target
的组合。 - 调整指针:如果当前和小于
target
,则c
向右移动;如果当前和大于target
,则d
向左移动。 - 记录结果:每当找到一个满足条件的四元组时,将其添加到结果集中。
代码:
#include <vector>
#include <algorithm> using namespace std; class Solution {
public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ans; int n = nums.size(); if (n < 4) { return ans; // 如果数组长度小于4,无法找到四元组,直接返回空结果 } sort(nums.begin(), nums.end()); // 对数组进行排序 // 固定前两个数 for (int a = 0; a < n - 3; ++a) { // 跳过重复的数字 if (a > 0 && nums[a] == nums[a - 1]) { continue; } // 提前终止:如果当前四个数的最小和大于target,则无需继续遍历 if ((long)nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) { break; } // 提前终止:如果当前a能取到的最大和小于target,则跳过当前的a if ((long)nums[a] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) { continue; } for (int b = a + 1; b < n - 2; ++b) { // 跳过重复的数字 if (b > a + 1 && nums[b] == nums[b - 1]) { continue; } // 提前终止:如果当前四个数的最小和大于target,则无需继续遍历b及其后的数 if ((long)nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target) { break; } // 提前终止:如果当前b能取到的最大和小于target,则跳过当前的b(但这里其实可以省略,因为外层a已经检查过了) // 但为了保持逻辑完整性,还是保留了这个检查 if ((long)nums[a] + nums[b] + nums[n - 2] + nums[n - 1] < target) { continue; } int d = n - 1; // 初始化右指针 // 固定第三个数,移动第四个数 for (int c = b + 1; c < n - 1; ++c) { // 跳过重复的数字 if (c > b + 1 && nums[c] == nums[c - 1]) { continue; } long sum = (long)nums[a] + nums[b] + nums[c] + nums[d]; // 计算当前和 // 如果当前和大于目标值,移动右指针 while (c < d && sum > target) { --d; sum = (long)nums[a] + nums[b] + nums[c] + nums[d]; // 更新当前和 } // 如果当前指针相遇,则无法再找到符合条件的四元组,跳出循环 if (c == d) { break; } // 如果找到符合条件的四元组,记录结果 if (sum == target) { ans.push_back({nums[a], nums[b], nums[c], nums[d]}); } } } } return ans; // 返回结果集 }
};
知识点摘要
- 排序:排序是处理数组问题时的常用技巧,有助于跳过重复元素和使用双指针技术。
- 双指针:在处理三个或更多数的和问题时,双指针技术可以大大减少时间复杂度。
- 边界条件:在处理数组问题时,要特别注意数组长度、指针移动范围等边界条件。
- 跳过重复:在固定某些数时,通过检查当前数是否与上一个数相同来跳过重复的组合。
- 提前终止:通过检查当前四个数的最小和与最大和是否满足目标值
target
来提前终止循环,减少不必要的计算。
补充:用(long)转换四数之和的结果是为了防止四数之和超过int的范围
四数之和问题是一个经典的算法问题,通过排序、双指针、跳过重复元素和提前终止等技巧,我们可以高效地解决这个问题。在本文中,我们详细分析了题目的思路,并给出了带有详细注释的代码实现。通过这些技巧,我们可以显著减少算法的时间复杂度,提高程序的运行效率。同时,这些技巧在处理其他类似的数组问题时也具有一定的参考价值。希望读者能够深入理解这些技巧,并在实际应用中灵活运用。