LeetCode - 4数之和
今天才发现，上周在钉钉上面加我的阿里同学，就是给我发offer的HR，而我当时并不知道，只知道去骚扰其他的HR问结果。
言归正传，这题是LeetCode第18题，中等难度，估计是我4月按顺序刷题的最后几题了...
原题地址：https://leetcode-cn.com/problems/4sum/
题目描述：
给定一个包含 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]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
我这种力量（暴力，无智慧）型选手，只能使用最笨的方法啦。本题采用的策略是固定两个指针，移动两个指针的方案。
- 先排序，排序之后，才好指针移动啊
- 确定两个固定指针分别指定i和j，i范围从0到倒数第四个，j从i+1到倒数第三个，注意跳过相同的值
- 然后确定两个移动指针l和r，l从j+1往右移动，r从最右边往左移动
- 计算nums[i] + nums[j] + nums[l] + nums[r]是否等于target（一开始审题没清楚，所以计算了是否等于0，导致解答错误），如果大了，就减小r；小了就增加l
中文官网题解：
https://leetcode-cn.com/problems/4sum/solution/
个人题解：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
Set<List<Integer>> sets = new HashSet<>();
for (int i = 0; i < nums.length - 3; i++) {
for (int j = i + 1; j < nums.length - 2; j++) {
if (i != 0 && nums[i] == nums[j] && nums[i] == nums[i - 1]) {
continue;
}
int l = j + 1;
int r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r] + nums[j];
if (sum == target) {
sets.add(Arrays.asList(nums[i], nums[l], nums[r], nums[j]));
l++;
r--;
} else if (sum > target) {
r--;
while (l < r && nums[r] == nums[r + 1]) {
r--;
}
} else {
l++;
while (l < r && nums[l] == nums[l - 1]) {
l++;
}
}
}
}
}
return new ArrayList<>(sets);
}
}结果：
可以很明显的看到，这个方法并不是很好，只超过了18%的人...
腾讯云开发者
