做二手车按揭的网站,网站建设设计哪家好,PHP调用wordpress数据库ID,网站开发设计培训价格#x1f341;你好#xff0c;我是 RO-BERRY #x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 #x1f384;感谢你的陪伴与支持 #xff0c;故事既有了开头#xff0c;就要画上一个完美的句号#xff0c;让我们一起加油 目录 前言1. 三数之和2. 解法你好我是 RO-BERRY 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 感谢你的陪伴与支持 故事既有了开头就要画上一个完美的句号让我们一起加油 目录 前言1. 三数之和2. 解法排序双指针3. 四数之和medium4. 解法排序 双指针 前言 双指针 常见的双指针有两种形式一种是对撞指针⼀种是左右指针。 对撞指针一般用于顺序结构中也称左右指针。 对撞指针从两端向中间移动。一个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。对撞指针的终止条件一般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是 left right 两个指针指向同一个位置 left right 两个指针错开 快慢指针又称为龟兔赛跑算法其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。 这种方法对于处理环形链表或数组非常有用。 其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使用快慢指针的思想。 快慢指针的实现方式有很多种最常用的⼀种就是
在一次循环中每次让慢的指针向后移动一位而快的指针往后移动两位实现一快一慢。 1. 三数之和
题目描述 给你一个整数数组 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 -105 nums[i] 105 2. 解法排序双指针
算法思路
本题与两数之和类似是非常经典的面试题。 与两数之和稍微不同的是题目中要求找到所有「不重复」的三元组。那我们可以利用在两数之和那里用的双指针思想来对我们的暴力枚举做优化
先排序然后固定⼀个数 a 在这个数后面的区间内使用「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意的是这道题里面需要有「去重」操作~
找到⼀个结果之后 left 和 right 指针要「跳过重复」的元素当使用完⼀次双指针算法之后固定的 a 也要「跳过重复」的元素
算法流程
先将 nums 排序时间复杂度为 O(NlogN)。
固定 333 个指针中最左最小元素的指针 k双指针 ij 分设在数组索引 (k,len(nums))(k, len(nums))(k,len(nums)) 两端。
双指针 iii , jjj 交替向中间移动记录对于每个固定指针 k 的所有满足 nums[k] nums[i] nums[j] 0 的 i,j 组合
当 nums[k] 0 时直接break跳出因为 nums[j] nums[i] nums[k] 0即 3 个元素都大于 0 在此固定指针 k 之后不可能再找到结果了。当 k 0且nums[k] nums[k - 1]时即跳过此元素nums[k]因为已经将 nums[k - 1] 的所有组合加入到结果中本次双指针搜索只会得到重复组合。 3.ij分设在数组索引 (k,len(nums))两端当i j时循环计算sum nums[k] nums[i] nums[j]并按照以下规则执行双指针移动 当s 0时i 1并跳过所有重复的nums[i] 当s 0时j - 1并跳过所有重复的nums[j] 当s 0时记录组合[k, i, j]至res执行i 1和j - 1并跳过所有重复的nums[i]和nums[j]防止记录到重复组合。
C代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint 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--;}}// 去重 ii;while (i n nums[i] nums[i - 1]) i;}return ret;}
};Java代码
class Solution
{public ListListInteger threeSum(int[] nums){ListListInteger 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 ArrayListInteger(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;}
}3. 四数之和medium
题目描述 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件 且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为 两个四元组重复 0 a, b, c, d na、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 4. 解法排序 双指针
前置题目: 请先完成三数之和。
思路: 思路和三数之和 一样排序后枚举 nums[a]作为第一个数枚举 nums[b] 作为第二个数那么问题变成找到另外两个数使得这四个数的和等于 target这可以用双指针解决。 对于 nums[a] 的枚举 设 snums[a]nums[a1]nums[a2]nums[a3]。如果 stargets由于数组已经排序后面无论怎么选选出的四个数的和不会比 s 还小所以后面不会找到等于 target的四数之和了。所以只要 stargets 就可以直接 break 外层循环了。 设 snums[a]nums[n−3]nums[n−2]nums[n−1]。如果 stargets 由于数组已经排序nums[a]加上后面任意三个数都不会超过 s所以无法在后面找到另外三个数与 nums[a]相加等于 target。但是后面还有更大的 nums[a]可能出现四数之和等于 target 的情况所以还需要继续枚举continue 外层循环。 如果 a0且 nums[a]nums[a−1]那么 nums[a] 和后面数字相加的结果必然在之前算出过所以无需执行后续代码直接 continue 外层循环。可以放在循环开头判断。
对于 nums[b] 的枚举b 从 a1 开始也同样有类似优化 设 snums[a]nums[b]nums[b1]nums[b2]。如果 stargets由于数组已经排序后面无论怎么选选出的四个数的和不会比 s 还小所以后面不会找到等于 target 的四数之和了。所以只要 stargets 就可以直接 break。 设 snums[a]nums[b]nums[n−2]nums[n−1]。如果 stargets由于数组已经排序nums[a]nums[b] 加上后面任意两个数都不会超过 s所以无法在后面找到另外两个数与 nums[a] 和 nums[b] 相加等于 target。但是后面还有更大的 nums[b]可能出现四数之和等于 target 的情况所以还需要继续枚举continue。 如果 ba1ba1ba1 且 nums[b]nums[b−1]那么 nums[b]\textit{nums}[b]nums[b] 和后面数字相加的结果必然在之前算出过所以无需执行后续代码直接 continue。注意这里 ba1 的判断是必须的如果不判断对于示例 2 这样的数据会直接 continue漏掉符合要求的答案。
对于 Java/C 等语言注意相加结果可能会超过 32 位整数范围需要用 64 位整数存储四数之和。 思路来自灵茶山艾府 C代码
class Solution
{
public:vectorvectorint fourSum(vectorint nums, int target){vectorvectorint 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 ListListInteger fourSum(int[] nums, int target){ListListInteger 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;}
}
