首页 > 代码库 > [LeetCode] 18. 4Sum
[LeetCode] 18. 4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]]
1 class Solution { 2 public: 3 vector<vector<int>> fourSum(vector<int>& nums, int target) { 4 vector<vector<int>> ret; 5 6 sort(nums.begin(), nums.end()); 7 8 // for i and j, need to avoid duplicates. 9 for (int i = 0; i < nums.size(); i++){10 if (i > 0 && nums[i] == nums[i-1]) continue;11 for (int j = i + 1; j < nums.size(); j++){12 // here j > ....13 if (j > i + 1 && nums[j] == nums[j-1]) continue;14 int left = j + 1;15 int right = nums.size() - 1;16 while (left < right){17 int tmp = nums[i] + nums[j] + nums[left] + nums[right];18 if (tmp < target){19 left++;20 }else if (tmp > target){21 right--;22 }else{23 vector<int> sol;24 sol.push_back(nums[i]);25 sol.push_back(nums[j]);26 sol.push_back(nums[left]);27 sol.push_back(nums[right]);28 ret.push_back(sol);29 left++;30 right--;31 while(nums[left] == nums[left-1]) left++;32 while(nums[right] == nums[right+1]) right--;33 }34 } 35 }36 }37 38 return ret;39 }40 };
[LeetCode] 18. 4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。