18、四数之和

题目：

解答：

同三数之和，但是外层两个for。

中间四个数相加需要用到long，并且逐个相加，防止溢出（这测试用例到底是谁写的）

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {int len = nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ans;for(int tar0=len-1;tar0>=3;){for(int tar1=tar0-1;tar1>=2;){int left =0,right=tar1-1;while(left<right){//这里得这么写，不然会overflowlong s = nums[left];s+=nums[right];s+=nums[tar0];s+=nums[tar1];if(s<target)left++;else if(s>target)right--;else {vector<int> temp(4);temp[0]=nums[left];temp[1]=nums[right];temp[2]=nums[tar0];temp[3]=nums[tar1];ans.push_back(temp);left++;while(nums[left]==nums[left-1]&&left<right)left++;}}tar1--;while(nums[tar1]==nums[tar1+1]&&tar1>=2)tar1--;}tar0--;while(nums[tar0]==nums[tar0+1]&&tar0>=3)tar0--;}return ans;}
};

时间复杂度O(n*n*n) n为nums长度

空间复杂度O(1)