本地网站后台管理建设/短视频seo排名
四数之和
力扣题目链接
题目描述
给你一个由 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
你可以按 任意顺序 返回答案 。
解题思路
这道题其实就是三数之和的进阶版，做完三数之和，这道题就会做了，就是在三数之和的前提上多加一层循环。
解题过程：
- 先对数组进行排序；
- 进行双循环遍历两个元素，在遍历这两个元素的时候都需要判断两次；
- 条件一为自己与上一个元素不相等，否则跳过这个元素；（防止元素重复）
- 条件二为该元素小于target或者小于0，否则直接结束循环；（这个元素已经大于target且大于0了，所以不可能组成一个答案）
- 然后和三数之和一样，定义做右指针在剩下范围的左右两侧，向中间收缩，直到左右指针相遇或者出现答案；
- 收缩时需要注意，如果出现和上一个元素相等的情况需要继续收缩，防止答案重复；
- 当出现所需要的答案时，保存在答案数组中即可。
题解
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ans;sort(nums.begin(), nums.end());for(int i = 0; i < nums.size(); i++){if(nums[i] > target && nums[i] > 0){break;}if(i > 0 && nums[i] == nums[i - 1]){continue;}for(int j = i + 1; j < nums.size(); j++){if(nums[i] + nums[j] > target && nums[i] + nums[j] > 0){break;}if(j > i + 1 && nums[j] == nums[j - 1]){continue;}int l = j + 1, r = nums.size() - 1;while(l < r){if((long)nums[i] + nums[j] + nums[l] + nums[r] == target){ans.push_back({nums[i], nums[j], nums[l], nums[r]});while(l < r && nums[r] == nums[r - 1]){r--;}while(l < r && nums[l] == nums[l + 1]){l++;}r--;l++;}else if((long)nums[i] + nums[j] + nums[l] + nums[r] > target){r--;}else if((long)nums[i] + nums[j] + nums[l] + nums[r] < target){l++;}}} } return ans;}
};
总结
在被三数之和反复折磨之后，算是理解了枝剪去重的操作，这次写四数之和的整体思路是对的，但是还是出现了很多小问题。力扣不能debug振刀好难受啊。