给定一个包含 n 个整数的数组 nums 和一个目标值 target, 判断 nums 中是否存在四个元素 a,b,c 和 d , 使得 a + b + c + d 的值与 target 相等? 找出所有满足条件且不重复的四元组.
注意:
答案中不可以包含重复的四元组.
题解: 先排序, 然后两层循环 i 从 0~n,j 从 i+1~n, 再取两个指针分别指向 j+1 和 n-1. 时间复杂度 O(n3)
- class Solution {
- public:
- vector<vector<int>> fourSum(vector<int>& nums, int target) {
- sort(nums.begin(),nums.end());
- vector<vector<int>> result;
- int len = nums.size();
- for(int i = 0; i <len; i++){
- if(i>0 && nums[i] == nums[i-1])
- continue;
- for(int j = i+1; j <len; j++){
- if(j>i+1 && nums[j] == nums[j-1])
- continue;
- int l = j+1;
- int r = len-1;
- while(l<r){
- if(nums[i] + nums[j] + nums[l] + nums[r] == target){
- result.push_back({nums[i],nums[j],nums[l],nums[r]});
- while(l<r && nums[l]==nums[l+1])
- l++;
- while(l<r && nums[r]==nums[r-1])
- r--;
- l++;
- r--;
- }
- else
- if(nums[i] + nums[j] +nums[l] + nums[r] <target){
- l++;
- }
- else
- if(nums[i] + nums[j] + nums[l] + nums[r]> target){
- r--;
- }
- }
- }
- }
- return result;
- }
- };
来源: http://www.bubuko.com/infodetail-3680250.html