卷进大厂系列之LeetCode刷题笔记:四数之和(中等)
学算法,刷力扣,加油卷,进大厂!
题目描述
力扣题目链接
给你一个由 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
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8输出:[[2,2,2,2]]
提示:
- 1 <= nums.length <= 200
- -109 <= nums[i] <= 109
- -109 <= target <= 109
涉及知识点
这是一道中等难度题目,与前面的三数之和有差不多的思路。很明显,直接for循环的暴力解法是超时的,但是对于这种我们想到的还是优化。参考三数之和的思路,我们依然可以通过使用双指针的方式来解决这道题目。
参考三数之和的解法,我们需要了解的知识点如下:
- 数组是存储在连续内存空间的相同类型数据的集合
- 数组下标都是从0开始
- 数组在内存空间的地址都是连续的
那么根据题目,我们可以提炼的关键点:
- 满足四数之和等于target
- 不重复
题目解答
Java题解一
思路分析
使用双指针法,即首先对数组排序,然后利用双指针的移动来找出满足条件的值(一共是四个指针,两个用来遍历的定指针)。具体思路如下:
- 首先排序,方便去重
- 第一个定指针 i,用来遍历(注意去重)
- 第二个定指针 j,用来遍历(注意去重)
- 开始使用双指针
- 然后是双指针的左右指针i和j,左指针i在k的后面,右指针j在数组最右边
- 在左右指针不交叉的情况下,左指针右移,右指针左移
- 满足条件加入List集合;不满足的话,移动固定指针后,重复上面步骤
代码实现如下
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { //双指针 List<List<Integer>> res = new ArrayList<>(); 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 left = j + 1; //左指针 int right = nums.length - 1; //右指针 while (left < right) { //满足左指针小于右指针 int sum = nums[i] + nums[j] + nums[left] + nums[right]; //sum求四数之和 if (sum == target) { //满足条件 res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // 跳过重复 while(left < right && nums[left+1] == nums[left]) left++; while (left < right && nums[right-1] == nums[right]) right--; // 左指针右移 left++; // 右指针左移 right--; } else if (sum > target) { //如果和比目标值大,移动右指针 right--; } else { // 如果和比目标值小,移动左指针 left++; } } } } return res; }}