【优选算法】（第四篇）

三数之和（medium）

题目解析

讲解算法原理

编写代码

四数之和（medium）

题目解析

讲解算法原理

编写代码

三数之和（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个整数数组nums，判断是否存在三元组[nums[i],nums[j],nums[k]]满⾜i!=j、i!=k且j!=k，同时还满⾜nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。
注意：答案中不可以包含重复的三元组。
⽰例1：输⼊：nums=[-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]
解释：nums[0]+nums[1]+nums[2]=(-1)+0+1=0。nums[1]+nums[2]+nums[4]=0+1+(-1)=0。nums[0]+nums[3]+nums[4]=(-1)+2+(-1)=0。不同的三元组是[-1,0,1]和[-1,-1,2]。
注意，输出的顺序和三元组的顺序并不重要。
⽰例2：输⼊：nums=[0,1,1]输出：[]
解释：唯⼀可能的三元组和不为0。
⽰例3：输⼊：nums=[0,0,0]输出：[[0,0,0]]
解释：唯⼀可能的三元组和为0。
提⽰：3<=nums.length<=3000-10^5<=nums[i]<=10^5

讲解算法原理

解法（排序+双指针）：算法思路：
本题与两数之和类似，是⾮常经典的⾯试题。
与两数之和稍微不同的是，题⽬中要求找到所有「不重复」的三元组。那我们可以利⽤在两数之和那⾥⽤的双指针思想，来对我们的暴⼒枚举做优化：
i. 先排序；
ii. 然后固定⼀个数 a ：
iii. 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意的是，这道题⾥⾯需要有「去重」操作~
i. 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
ii. 当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素

编写代码

c++算法代码；

class Solution
{
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;// 1. 排序sort(nums.begin(), nums.end());// 2. 利⽤双指针解决问题int n = nums.size();for(int i = 0; i < n; ) // 固定数 a{if(nums[i] > 0) break; // ⼩优化int left = i + 1, right = n - 1, target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else{ret.push_back({nums[i], nums[left], nums[right]});left++, right--;// 去重操作 left 和 rightwhile(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) 
right--;}}// 去重 i i++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;}
};

java 算法代码：

class Solution
{public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();// 1. 排序Arrays.sort(nums);// 2. 利⽤双指针解决问题int n = nums.length;for(int i = 0; i < n; ) // 固定数 a{if(nums[i] > 0) break; // ⼩优化int left = i + 1, right = n - 1, target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else{// nums[i] nums[left] num[right]ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], 
nums[left], nums[right])));left++; right--; // 缩⼩区间继续寻找// 去重：left rightwhile(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) 
right--;}}// 去重：ii++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;}
}

四数之和（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个由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

讲解算法原理

解法（排序+双指针）
算法思路：
a. 依次固定⼀个数 a ；
b. 在这个数 a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于 target
- a 即可。

编写代码

c++算法代码：

class Solution
{
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;// 1. 排序sort(nums.begin(), nums.end());// 2. 利⽤双指针解决问题int n = nums.size();for(int i = 0; i < n; ) // 固定数 a{// 利⽤ 三数之和for(int j = i + 1; j < n; ) // 固定数 b{// 双指针int left = j + 1, right = n - 1;long long aim = (long long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum < aim) left++;else if(sum > aim) right--;else{ret.push_back({nums[i], nums[j], nums[left++], 
nums[right--]});// 去重⼀while(left < right && nums[left] == nums[left - 1]) 
left++;while(left < right && nums[right] == nums[right + 1]) 
right--;}}// 去重⼆j++;while(j < n && nums[j] == nums[j - 1]) j++;}// 去重三i++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;}
};

java 算法代码实现：

class Solution
{public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ret = new ArrayList<>();// 1. 排序Arrays.sort(nums);// 2. 利⽤双指针解决问题int n = nums.length;for(int i = 0; i < n; ) // 固定数 a{// 三数之和for(int j = i + 1; j < n; ) // 固定数 b{// 双指针int left = j + 1, right = n - 1;long aim = (long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum > aim) right--;else if(sum < aim) left++;else{ret.add(Arrays.asList(nums[i], nums[j], nums[left++], 
nums[right--]));// 去重⼀while(left < right && nums[left] == nums[left - 1]) 
left++;while(left < right && nums[right] == nums[right + 1]) 
right--;}}// 去重⼆j++;while(j < n && nums[j] == nums[j - 1]) j++;}// 去重三i++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;}
}