Leetcode18及关于算法的一些思索
Page content
题目描述
给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]:
-
0 <= a, b, c, d <= n -
a, b, c, d互不相同 -
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案。
题目链接：https://leetcode-cn.com/problems/4sum/
思路分析
本题与leetcode15题三数之和十分相似，对于三数之和问题，我也在之前的文章中进行了叙述https://mananbc1st.github.io/posts/leetcode15/，其主体算法思想为排序+贪心的策略（三指针求解）。
那么对于四数之和可以看作是三数之和问题的推广，理解了其求解的方式，你可以写出N数之和的算法。
如何从已知的三数之和问题为条件去求解四数之和乃至N数之和的问题呢？
主要思想还是讲问题分解为可以求解的子问题，也就是问题归约法
具体的实现逻辑为：递归 + 回溯。
Java AC代码
private final List<List<Integer>> res = new ArrayList<>();
private void doSearchOpt(int[] nums, int start, int target, List<Integer> container) {
if (container.size() == 1) {
// 只要将问题递归至三数之和问题，就达到了算法的递归基
// 因为三数之和问题有解
for (int i = start; i < nums.length; ++i) {
if (i > start && nums[i] == nums[i - 1]) continue; // 去重
int j = i + 1, k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum > target){
k--;
} else if (sum < target) {
j++;
}else {
res.add(List.of(container.get(0), nums[i], nums[j], nums[k]));
// 去重
while (j < k && nums[j] == nums[j + 1]) j ++;
while (j < k && nums[k] == nums[k - 1]) k --;
j++; k--;
}
}
}
return;
}
for (int i = start; i < nums.length; ++i) {
container.add(nums[i]);
doSearchOpt(nums, i + 1, target - nums[i], container);
container.remove(container.size() - 1); // 回溯
while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++; // 去重
}
}
public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums.length < 4) return res;
Arrays.sort(nums);
doSearchOpt(nums, 0, target, new ArrayList<>());
return res;
}
问题归约法
已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。
问题归约法是从目标出发逆向推理，建立子问题以及子问题的子问题，直至最后把出事问题归约为一个平凡的本源问题集合，这就是问题归约的实质。
