ze(); ) {
for (int j = i+1; j < nums.size(); ) {
int targetVal = 0 - nums[i] - nums[j];
if (nums2Ind.count(targetVal) != 0 && nums2Ind[targetVal] > i && nums2Ind[targetVal] > j) {
resVec.emplace_back(vector<int>{nums[i], nums[j], targetVal});
}
j++;
while (j < nums.size() && nums[j] == nums[j - 1]) {
j++;
}
}
i++;
while (i < nums.size() && nums[i] == nums[i - 1]) {
i++;
}
}
return resVec;
}
两种方法,细致来看看,还是第一种方法更为简略。
给你一个由 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
你可以按 任意顺序 返回答案 。
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
约束:
1 <= nums.length <= 200
- \(-10^9 <= nums[i] <= 10^9\)
- \(-10^9 <= target <= 10^9\)
用三数之和的方法解决四数之和的问题,注意可能会越界的问题int64_t tmpSum = static_cast<int64_t>(nums[a]) + nums[b] + nums[c] + nums[d];
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end(), [&](const int &a, const int &b) {
return a < b;
});
vector<vector<int>> resVec;
if (nums.size() < 4) {
return resVec;
}
for (int a = 0; a < nums.size() - 3; ) {
if (nums[a] > target && nums[a] > 0) {
return resVec;
}
for (int b = a + 1; b < nums.size() - 2; ) {
int c = b + 1;
int d = nums.size() - 1;
while (c < d) {
int64_t tmpSum = static_cast<int64_t>(nums[a]) + nums[b] + nums[c] + nums[d];
if (tmpSum == target) {
resVec.emplace_back(vector<int>{nums[a], nums[b], nums[c], nums[d]});
c++;
while (c < d && nums[c] == nums[c-1]) {
c++;
}
d--;
while (c < d && nums[d] == nums[d+1]) {
d--;
}
} else if (tmpSum > target) {
d--;
while (c < d && nums[d] == nums[d+1]) {
d--;
}
} else {
c++;
while (c < d && nums[c] == nums[c-1]) {
c++;
}
}
}
b++;
while (b < nums.size() - 2 && nums[b] == nums[b - 1]) {
b++;
}
}
a++;
while (a < nums.size() - 3 && nums[a] == nums[a - 1]) {
a++;
}
}
return resVec;
}
-
解释下,tmpSum为什么用int不行,需要用int64_t
int的取值范围为:
有符号数,最高位为符号位;共占用4字节,即32bit。所以,表示范围为:\(-2^{31}\) ~ \(2^{31}-1\)。
\(2^{31} = 2147483648 = 2.x * 10^9\)
因为:\(-10^9 <= nums[i] <= 10^9\)
所以,四个nums[i]相加可能会越界,需要用更高精度的方法表示。
int64_t,占用64bit,除去最高位的符号位,表示范围为:\(-2^{63}\) ~ \(2^{63}-1\)。
\(2^{63} = 9,223,372,036,854,775,808= 9.x * 10^{18}\)
给定两个数组 nums1
和 nums2
,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
约束:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
首先,去重;去重后,遍历其中一个数组,然后判断某个元素在另外一个数组中是否存在,从而找到交集。
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end());
unordered_map<int, int> nums2Ind;
for (size_t i = 0; i < nums2.size(); i++) {
nums2Ind[nums2[i]] = i;
}
vector<int> resVec;
for (size_t i = 0; i < nums1.size(); i++) {
if (nums2Ind.count(nums1[i]) != 0) {
resVec.emplace_back(nums1[i]);
}
}
return resVec;
}