Leetcode-＞18四数之和-创新互联

题目

在这里插入图片描述

站在用户的角度思考问题，与客户深入沟通，找到舟曲网站设计与舟曲网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站设计制作、网站建设、企业官网、英文网站、手机端网站、网站推广、域名与空间、虚拟空间、企业邮箱。业务覆盖舟曲地区。算法思路及代码实现

方法：排序加双指针
本题与「15. 三数之和」相似，解法也相似。
在这里插入图片描述

代码实现

#include#include#include 
using namespace std;

class Solution {public:
    vector>fourSum(vector& nums, int target) {vector>quadruplets;
        if (nums.size()< 4) {return quadruplets;
        }
        sort(nums.begin(), nums.end());
        int length = nums.size();
        for (int i = 0; i< length - 3; i++) {if (i >0 && nums[i] == nums[i - 1]) {continue;
            }
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] >target) {break;
            }
            if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1]< target) {continue;
            }
            for (int j = i + 1; j< length - 2; j++) {if (j >i + 1 && nums[j] == nums[j - 1]) {continue;
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] >target) {break;
                }
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1]< target) {continue;
                }
                int left = j + 1, right = length - 1;
                while (left< right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left< right && nums[left] == nums[left + 1]) {left++;
                        }
                        left++;
                        while (left< right && nums[right] == nums[right - 1]) {right--;
                        }
                        right--;
                    } else if (sum< target) {left++;
                    } else {right--;
                    }
                }
            }
        }
        return quadruplets;
    }
};


int main()
{Solution solution;
    vectornums = {1,0,-1,0,-2,2};
	int target = 0;
    vector>result = solution.fourSum(nums,target);
   for (vector>::iterator it = result.begin(); it != result.end(); it++)
   {  for (vector::iterator itit = (*it).begin(); itit != (*it).end(); itit++)
	  {cout<< *itit<< " ";
      }	
      cout<< endl;	
   }
 
    return 0;
}