乘风破浪：LeetCode真题_018_4Sum
一、前言
前面我们已经练习过了三个数相加的集合运算，现在变成了四个数，其实道理是一样的。三个数的时候可以转成两个数的加法，最后来解决，而四个数的可以转换成三个数的加法，最终变成两个数的加法运算。
二、4Sum
2.1 问题
2.2 分析与解决
根据我们之前的经验，可以很自然地想到变成三个数相加来计算，不过因为是四个数相加，因此需要至少3个循环了，这样时间复杂度就是O(n~3)。下面是这种解法。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
if (nums.length == 0) return ans;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = nums.length - 1;
while (k < l) {
int sum = nums[i] + nums[j] + nums[k] + nums[l];
if (sum < target) k++;
else if (sum > target) l--;
else {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
list.add(nums[l]);
ans.add(list);
if (nums[k] == nums[l]) break;
while (k + 1 < l && nums[k] == nums[k + 1]) k++;
while (l - 1 > k && nums[l] == nums[l - 1]) l--;
k++;
l--;
}
}
}
}
return ans;
}
}
另外我们也可以做一些细节上面优化，这里不再赘述。
三、总结
对于一些类型题，我们只要理解了一些本质，并且在做题的时候多联想一些之前的道理，就能轻松地做出来了。万事开头难，思路是非常重要的。