排序 + 双指针
解题思路
基于 leetcode🧑💻 15. 三数之和 的解题思路，在外层再嵌套一层循环；
先固定两个指针 i、j ，再滑动另外两个指针 left、right 进行求和；
代码实现
var fourSum = function (nums, target) {
const res = [];
if (nums.length < 4) return res;
nums.sort((x, y) => x - y);
const length = nums.length;
for (let i = 0; i < length - 3; i++) {
// 第一个指针的数字去重
if (i > 0 && nums[i] === nums[i - 1]) continue;
// 由于数组已经排序，选出最小的四个数都已经大于了 target，后面不会找到 等于 target 的组合了
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
// 由于数组已经排序，选出最大的四个数都已经小于了 target，后面不会找到 等于 target 的组合了
if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) continue;
for (let j = i + 1; j < length - 2; j++) {
// 第二个指针的数字去重
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
// 由于数组已经排序，选出最小的四个数都已经大于了 target，后面不会找到 等于 target 的组合了
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
// 由于数组已经排序，选出最大的四个数都已经小于了 target，后面不会找到 等于 target 的组合了
if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) continue;
let left = j + 1, right = length - 1;
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum === target) {
res.push([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 res;
};
回溯
解题思路
求满足下述全部条件且不重复的四元组：
nums[a] + nums[b] + nums[c] + nums[d] == target；- a、b、c 和 d 互不相同；
比较子集（数组）的异同非常耗时，需要先 排序数组 ，再比较数组中每个元素的异同，
重复子集剪枝：
- 分支 1：如果第一轮选择了 2 ，第二轮选择了 3 ，则记为 [2,3,XX]；
- 分支 2：如果第一轮选择了 3 ，第二轮选择了 2 ，则记为 [3,2,XX] ，那这样就会出现重复集合，第二轮应该跳过 2，从 3 开始；
解决步骤二的问题，可以定义一个 startInx 索引，每次递归传入 startInx 索引，这样就可以跳过前面的索引，避免重复集合；
终止条件：
target = target - path 中的元素，target 为 0 的时候就说明 path 中的元素满足条件，放入结果中；
剪枝：
- 剩下可选的数字个数 < 需要选择的数字个数，即 nums.length - startInx < count；
- count 个最小值都大于 target；
- count 个最大值都小于 target；
代码实现
var fourSum = function (nums, target) {
let res = [];
nums.sort((a, b) => a - b);
backtrack(res, nums, 0, 4, target, []);
return res;
};
/**
* @param {*} res 结果
* @param {*} nums 原始数组
* @param {*} startInx 开始索引
* @param {*} count 计算个数（4数之和）
* @param {*} target 目标值
* @param {*} path 路径数据
* @returns
*/
const backtrack = (res, nums, startInx, count, target, path) => {
// 终止条件：target = target 减去 path 中的元素，targte 为 0，即求出了 nums[a] + nums[b] + nums[c] + nums[d] == target
if (count === 0 && target === 0) {
res.push([...path]);
return;
}
// 剪枝：剩下可选的数字个数 < 需要选择的数字个数
if (nums.length - startInx < count) return;
// 剪枝：count 个最小值都大于 target
if (count * nums[startInx] > target) return;
// 剪枝：count 个最大值都小于 target
if (count * nums[nums.length - 1] < target) return;
for (let i = startInx; i < nums.length; i++) {
// 剪枝：重复元素
if (startInx < i && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
backtrack(res, nums, i + 1, count - 1, target - nums[i], path);
path.pop();
}
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
1572.矩阵对角线元素的和
上一篇
评论
