携程网站建设计划管理与进度控制,微站和网站数据同步,wordpress添加用户关闭邮箱,36kr wordpress主题1三数之和
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元…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 。
思路
首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。
在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。
接下来如何移动left 和right呢 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。
如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。
本题解题思路重点是去重
外层循环中的条件判断在每次循环开始时通过判断当前数字与前一个数字是否相同来避免重复计算相同的数字。如果当前数字与前一个数字相同则跳过当前循环继续下一个数字的处理。 if(i 0 nums[i] nums[i - 1])continue; 内层循环中的去重操作在找到符合条件的三元组后通过向右移动左指针和向左移动右指针并跳过与移动后相同的元素来避免重复。 while(left right nums[left] nums[left 1])left;while(left right nums[right] nums[right - 1])right--;
完整代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ans; // 用于存储结果的二维向量// 对数组进行排序方便后续操作sort(nums.begin(), nums.end());// 遍历数组for(int i 0; i nums.size(); i) {// 避免重复计算相同的数字if(i 0 nums[i] nums[i - 1])continue;int left i 1; // 左指针指向当前数字的下一个位置int right nums.size() - 1; // 右指针指向数组末尾int target 0 - nums[i]; // 目标值为当前数字的相反数// 在左右指针没有相遇的情况下进行查找while(left right) {// 如果找到了三个数的和等于目标值if(nums[left] nums[right] target) {// 将结果加入到答案中ans.push_back({nums[i], nums[left], nums[right]});// 继续查找下一个不同的左指针值while(left right nums[left] nums[left 1])left;// 继续查找下一个不同的右指针值while(left right nums[right] nums[right - 1])right--;// 向中间收缩left;right--;} // 如果三数之和小于目标值则左指针向右移动else if(nums[left] nums[right] target) {left;} // 如果三数之和大于目标值则右指针向左移动else {right--;}}}return ans; // 返回结果}
};
2四数之和
给你一个由 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
思路 剪枝处理在这里剪枝指的是通过判断当前数值是否已经大于目标值或者非负且大于等于目标值如果是的话就可以跳出循环因为后面的数值只会更大不会再符合条件了。这里使用break语句跳出循环统一通过return返回最终结果。 对nums[k]去重这里的去重处理是指如果当前数字与前一个数字相同除了第一个数字外则跳过当前循环继续下一个数字的处理以避免重复计算相同的数字。 2级剪枝处理类似于剪枝处理这里也是对两个数字的和进行判断如果已经大于目标值或者非负且大于等于目标值则跳出循环因为后面的数值只会更大不会再符合条件了。 对nums[i]去重与对nums[k]去重类似这里是对内层循环中的第二个数字进行去重处理避免重复计算相同的数字。 对nums[left]和nums[right]去重在找到符合条件的四元组后通过向右移动左指针和向左移动右指针并跳过与移动后相同的元素来避免重复。
代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {// 存储结果的二维向量vectorvectorint result;// 对数组进行排序方便后续处理sort(nums.begin(), nums.end());// 外层循环遍历数组for (int k 0; k nums.size(); k) {// 剪枝处理如果当前数字已经大于目标值且为非负数跳出循环if (nums[k] target nums[k] 0) {break; // 这里使用break统一通过最后的return返回}// 对当前数字进行去重处理if (k 0 nums[k] nums[k - 1]) {continue;}// 内层循环遍历数组for (int i k 1; i nums.size(); i) {// 2级剪枝处理如果当前两个数字的和已经大于目标值且为非负数跳出循环if (nums[k] nums[i] target nums[k] nums[i] 0) {break;}// 对第二个数字进行去重处理if (i k 1 nums[i] nums[i - 1]) {continue;}// 定义左右指针int left i 1;int right nums.size() - 1;// 在左右指针未相遇之前进行循环while (right left) {// 避免溢出使用 long 类型进行判断if ((long) nums[k] nums[i] nums[left] nums[right] target) {right--;} else if ((long) nums[k] nums[i] nums[left] nums[right] target) {left;} else {// 找到符合条件的四元组加入结果向量result.push_back(vectorint{nums[k], nums[i], nums[left], nums[right]});// 对左右指针所指的数字进行去重处理while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;// 找到答案时双指针同时收缩right--;left;}}}}// 返回最终结果return result;}
};
3移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作
更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。
用户评测
评测机将使用以下代码测试您的解决方案
int[] nums [...]; // 输入数组
int val ...; // 要移除的值
int[] expectedNums [...]; // 长度正确的预期答案。// 它以不等于 val 的值排序。int k removeElement(nums, val); // 调用你的实现assert k expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i 0; i actualLength; i) {assert nums[i] expectedNums[i];
}
如果所有的断言都通过你的解决方案将会 通过。 示例 1
输入nums [3,2,2,3], val 3
输出2, nums [2,2,_,_]
解释你的函数函数应该返回 k 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。
示例 2
输入nums [0,1,2,2,3,0,4,2], val 2
输出5, nums [0,1,4,0,3,_,_,_]
解释你的函数应该返回 k 5并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。提示
0 nums.length 1000 nums[i] 500 val 100
思路
慢指针 slowIndex 指向下一个待赋值的位置快指针 fastIndex 遍历数组。当快指针指向的元素不等于目标值时将其赋值给慢指针指向的位置并将慢指针向后移动一位。这样就实现了移除数组中指定值的元素并且返回新数组的长度
代码
class Solution {
public:// 移除元素函数int removeElement(vectorint nums, int val) {// 慢指针初始位置int slowIndex 0;// 快指针遍历数组for (int fastIndex 0; fastIndex nums.size(); fastIndex) {// 如果当前值不等于目标值if (val ! nums[fastIndex]) {// 将当前值移到慢指针位置并将慢指针向后移动一位nums[slowIndex] nums[fastIndex];}}// 返回新数组的长度return slowIndex;}
};
4反转字符串
编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 示例 1
输入s [h,e,l,l,o]
输出[o,l,l,e,h]示例 2
输入s [H,a,n,n,a,h]
输出[h,a,n,n,a,H] 提示
1 s.length 105s[i] 都是 ASCII 码表中的可打印字符
代码
class Solution {
public:void reverseString(vectorchar s) {for (int i 0, j s.size() - 1; i s.size()/2; i, j--) {swap(s[i],s[j]);}}
};
