LeetCode18.四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

双指针法

四数之和转三数之和，再转两数之和

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; sort(nums.begin(), nums.end()); //首先排序 if (nums.empty()) return {}; for(int z = 0; z < nums.size(); z ++){ if (z > 0 && nums[z] == nums[z - 1]) continue; int newTarget = target - nums[z]; // 将四数之和转化为3数 for(int k = z+1; k < nums.size(); k++){ // 三数变成两数 if(k > z+1 && nums[k] == nums[k - 1]) continue; int newTarget2 = newTarget - nums[k]; int i = k + 1, j = nums.size() - 1; while (i < j) { // 两数之和直接套用《两数之和2》的题 if (nums[i] + nums[j] == newTarget2) { res.push_back({nums[z], nums[k], nums[i], nums[j]}); while (i < j && nums[i] == nums[i + 1]) ++i; //注意去重 while (i < j && nums[j] == nums[j - 1]) --j; ++i; --j; } else if (nums[i] + nums[j] < newTarget2) ++i; else --j; } } } return res; } };

回溯法

首先将 nums 升序排序，并把答案四元组中没确定的个数设为 n

我把剪枝分为了 4 类，括号内的是用什么完成剪枝

如果剩余可选的数字数量少于 n，则剪掉（递归返回）；每层递归中，从第二轮循环开始，如果数组中当前数字和前一个相同，则剪掉（进行下一次循环，这条的任务就是去重）；如果 当前数字 + 已确定数字的和 + (n - 1) * 排序后数组中当前数字的下一个数字 > target，则说明后面的数无论怎么选，加起来都一定大于 target，所以剪枝（递归返回）；如果 当前数字 + 已确定数字的和 + (n - 1) * 排序后数组最后一个数字 < target，则说明当前数字不能选，当前数字加后面的数字都一定小于 target ，所以剪枝（进行下一次循环）；

cpp版

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution_18_001 { private: vector<vector<int>> ans;//结果集 vector<int> nums; //排序后的数组 vector<int> path; //路径 int target;//目标 int numSize;//数组长度 void dfs(int idx, int sum) { //满足4个数之和 if (sum == target && path.size() == 4) { ans.emplace_back(path); return; } for (int i = idx; i < numSize; ++i) { if (numSize - i < int(4 - path.size())) //剪枝 return; if (i > idx && nums[i] == nums[i - 1]) //去重 continue; if (i < numSize - 1 && (sum + nums[i] + int(3 - path.size()) * nums[i + 1] )> target) //剪枝 return; if (i < numSize - 1 && (sum + nums[i] + int(3 - path.size()) * nums[numSize - 1]) < target) //剪枝 continue; //添加到路径中 path.emplace_back(nums[i]); //深度优先搜索 dfs(i + 1, sum + nums[i]); //回溯，从路径中移除 path.pop_back(); } return; } public: vector<vector<int>> fourSum(vector<int> &nums, int target) { sort(nums.begin(), nums.end()); this->nums = nums; //复制一下，不破坏原来的nums this->target = target; //复制一下，不破坏原来的target this->numSize = nums.size(); if (numSize < 4) return ans; dfs(0, 0); return ans; } }; int main() { //vector初始方案1 // vector<int> nums; //1, 0, -1, 0, -2, 2 // nums.push_back(1); // nums.push_back(0); // nums.push_back(-1); // nums.push_back(0); // nums.push_back(-2); // nums.push_back(2); //vector初始方案2 int arr[] = {1, 0, -1, 0, -2, 2}; vector<int> nums(arr, arr + sizeof(arr) / sizeof(int)); //执行四数求和 Solution_18_001 s; vector<vector<int>> vvec; vvec = s.fourSum(nums, 0); //打印结果 vector<vector<int>>::iterator vv = vvec.begin(); while (vv != vvec.end()) { vector<int>::iterator v = (*vv).begin(); while (v != (*vv).end()) { std::cout << *v << "\t"; v++; } std::cout << std::endl; vv++; } }

java版

// "static void main" must be defined in a public class. public class Main { private List<List<Integer>> res;//结果集 private int target;//目标 public List<List<Integer>> fourSum(int[] nums, int target) { res = new ArrayList<>(); Arrays.sort(nums); // 排序便于剪枝操作 this.target = target; helper(nums, 0, 0, new ArrayList<>()); return res; } private void helper(int[] nums, int index, int target, List<Integer> list) { if (list.size() == 4 && target == this.target) { // 如果数量相等，且和等于target，直接放入结果中 res.add(new ArrayList<>(list)); return; } for (int i = index; i < nums.length; i++) { // 后续数量如果已经凑不齐4个，直接剪掉 if (nums.length - i < 4 - list.size()) return; // 避免重复结果 if (i > index && nums[i] == nums[i - 1]) continue; // 这里借鉴了官方题解评论中一位大哥的写法，这样可以精简代码，否则(3 - list.size()) * nums[i + 1]要写成好几个if条件，这样会粗略一些，不过应该还好 if (i < nums.length - 1 && (target + nums[i] + (3 - list.size()) * nums[i + 1] ) > this.target) return; // 这里同上 if (i < nums.length - 1 && (target + nums[i] + (3 - list.size()) * nums[nums.length - 1] ) < this.target) continue; // 下方的代码就是经典的回溯代码了，不再赘述 list.add(nums[i]); helper(nums, i + 1, target + nums[i], list); list.remove(list.size() - 1); } } public static void main(String[] args) { Main s = new Main(); int[] nums = {1, 0, -1, 0, -2, 2}; List<List<Integer>> list = s.fourSum(nums,0); System.out.println(list); } }

参考

leetcode leetcode.46.全排列——回溯算法+dfs 全排列 ll (Permutations II)——回溯算法+dfs emplace_back() 和 push_back 的区别