leetcode18--四数之和

2024-03-14 18:28

文章标签 四数 leetcode18

本文主要是介绍leetcode18--四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

求所有数组中四个数之和为指定值的所有组合

四数之和

2. 题解

暴力没想到也能过

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {std::sort(nums.begin(), nums.end());vector<vector<int>> ans;int sz = nums.size();for (int i = 0;i < sz; ++i) {if (i > 0 && nums[i] == nums[i - 1])continue;for (int j = i + 1;j < sz; ++j) {if (j > i + 1 && nums[j] == nums[j - 1])continue;int lp = j + 1;int rp = sz - 1;long long tot = (long long) nums[i] + nums[j];while (lp < rp) {long long rest = nums[lp] + nums[rp];if ( tot + rest == target) {ans.push_back({nums[i],nums[j],nums[lp],nums[rp]});++lp;--rp;while (lp< rp && nums[lp] == nums[lp-1]) {++lp;}while (lp < rp && nums[rp] == nums[rp+1]){--rp;}}else if (tot + rest  < target) {lp++;}else {rp--;}}}}return ans;}
};

双指针: 注意处理相等时的情况，需要左右指针都移到与上一位置不同的地方。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {std::sort(nums.begin(), nums.end());vector<vector<int>> ans;int sz = nums.size();for (int i = 0;i < sz; ++i) {if (i > 0 && nums[i] == nums[i - 1])continue;for (int j = i + 1;j < sz; ++j) {if (j > i + 1 && nums[j] == nums[j - 1])continue;int lp = j + 1;int rp = sz - 1;long long tot = (long long) nums[i] + nums[j];while (lp < rp) {long long rest = nums[lp] + nums[rp];if ( tot + rest == target) {ans.push_back({nums[i],nums[j],nums[lp],nums[rp]});++lp;--rp;while (lp< rp && nums[lp] == nums[lp-1]) {++lp;}while (lp < rp && nums[rp] == nums[rp+1]){--rp;}}else if (tot + rest  < target) {lp++;}else {rp--;}}}}return ans;}
};