昆山网站建设公司怎么样,wordpress 不能查看站点,wordpress 百度插件怎么用,简书网站开发文章目录 #x1f4cb;前言#x1f3af;两数之和 II#x1f4da;题目内容✅解答 #x1f3af;移除元素#x1f4da;题目内容✅解答 #x1f3af;有序数组的平方#x1f4da;题目内容✅解答 #x1f3af;三数之和#x1f4da;题目内容✅解答 #x1f4dd;最后 #x… 文章目录 前言两数之和 II题目内容✅解答 移除元素题目内容✅解答 有序数组的平方题目内容✅解答 三数之和题目内容✅解答 最后 前言
这个系列的文章收纳的内容是来自于蓝桥云课的前端岗位笔面必刷题的内容简介是30天133题本题单题目全部来自于近2年BAT等大厂前端笔面真题因为部分题目是需要会员所以该系列的文章内容并非完全全面如果需要会员的题目则从 leetcode 补充对应的题目题目大概也是一样的考法。文章中题目涉及的内容包括原题、答案和解析等等。 两数之和 II
题目内容
给你一个下标从 1 开始的整数数组 numbers 该数组已按非递减顺序排列请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入只对应唯一的答案而且你不可以重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
输入numbers [2,7,11,15], target 9
输出[1,2]
解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2]。输入numbers [2,3,4], target 6
输出[1,3]
解释2 与 4 之和等于目标数 6 。因此 index1 1, index2 3 。返回 [1, 3]。输入numbers [-1,0], target -1
输出[1,2]
解释-1 与 0 之和等于目标数 -1 。因此 index1 1, index2 2 。返回 [1, 2]。题目给的测试用例里有以下限制
2 numbers.length 4。-1 numbers[i] 15。numbers 按非递减顺序排列。-1 target 17。仅存在一个有效答案。
✅解答
初始提供代码
function twoSum2(nums, target) {// 补充代码
}答案 这题跟两数之和的题目还是差不多的思路的但是要注意这题的要求和限制条件。我们可以在两数之和那一题的基础上继续修改注意看题目说到的 “下标从 1 开始” 因此我们在返回下标地址的时候要留意。代码如下。
function twoSum2(nums, target) {for(let i0;inums.length;i){for(let ji1;jnums.length;j){if(nums[i]nums[j]target){return [i1,j1]}}}
}这个解法实现了暴力枚举法来解决数组两数之和的问题时间复杂度为 O(n^2)。具体来说它双重循环遍历数组将每一对不同的元素相加判断它们的和是否等于目标数 target如果相等则找到了答案返回两个元素的下标即可。虽然暴力枚举法思路简单但时间复杂度较高因此我们可以用双指针的方法来解这一题。
另一种解法
function twoSum2(numbers, target) {let left 0, right numbers.length - 1;while (left right) {const sum numbers[left] numbers[right];if (sum target) {left;} else if (sum target) {right--;} else {return [left 1, right 1]; }}
}因为数组已按照非递减顺序排列所以可以考虑使用双指针分别从数组的两端开始向中间移动每次比较两个指针所指的元素之和与目标数 target 的大小关系如果和小于 target则左指针右移使得和增大如果和大于 target则右指针左移使得和减小如果和等于 target则找到了答案返回两个指针的下标即可。
具体的实现细节如下
定义左指针 left 和右指针 right初始时分别指向数组的第一个元素和最后一个元素当 left right 时若 numbers[left] numbers[right] target则将 left因为数组已按照非递减顺序排列所以左指针右移可以使得和增大若 numbers[left] numbers[right] target则将 right--同样理由右指针左移可以使得和减小若 numbers[left] numbers[right] target则找到了答案返回 [left, right]。
该函数的时间复杂度为 O(n) 其中 n 是数组的长度因为在最坏情况下需要遍历整个数组一次。空间复杂度为 O(1)这个解法优于第一种暴力枚举的解法只不过算法题练习能解开有思路都是可以的。 移除元素
题目内容
给你一个数组 nums 和一个值 val你需要原地移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入nums [3,2,2,3], val 3
输出2, nums [2,2]
解释函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums [2,2,3,3] 或 nums [2,2,0,0]也会被视作正确答案。输入nums [0,0,1,1,1,2,2,3,3,4]
输出5, nums [0,1,2,3,4]
解释函数应该返回新的长度 5 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。题目给的测试用例里有以下限制
1 nums.length 8。0 nums[i] 4。1 val 3。
✅解答
初始提供代码
function removeElement(nums, val) {// 补充代码
}答案
function removeElement(nums, val) {let j 0;for (let i 0; i nums.length; i) {if (nums[i] ! val) {nums[j] nums[i];j;}}return j;
}这一题可以使用双指针来解决。首先定义两个指针 i 和 j初始时都指向数组的第一个元素。然后遍历整个数组如果当前元素不等于要移除的元素则将其放到数组前面即将 nums[j] nums[i]并同时将 j 右移一位表示下一个非要移除的元素需要存放的位置。遍历完成后j 的值就是新数组的长度因为 0 到 j - 1 就是新数组中的元素而 j 到最后都是多余的。最后返回 j 即可。
该函数的时间复杂度为 O(n)其中 n 是数组的长度。遍历一次数组时间复杂度是 O(n)。空间复杂度为 O(1)。只使用了常数个变量符合题目的要求。 接下来两题要会员了所以题目源自 leetcode题目考法基本是一样的 有序数组的平方
题目内容
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例一
输入nums [-4,-1,0,3,10]
输出[0,1,9,16,100]
解释平方后数组变为 [16,1,0,9,100]
排序后数组变为 [0,1,9,16,100]示例二
输入nums [-7,-3,2,3,11]
输出[4,9,9,49,121]提示与限制
1 nums.length 104。-104 nums[i] 104。nums 已按 非递减顺序 排序。
进阶 请你设计时间复杂度为 O(n) 的算法解决本问题
✅解答
初始提供代码
var sortedSquares function(nums) {};答案
var sortedSquares function(nums) {let n nums.length;let res new Array(n);let left 0, right n - 1; // 双指针分别指向数组左右两端for (let i n - 1; i 0; i--) { // 从后往前遍历if (Math.abs(nums[left]) Math.abs(nums[right])) { // 左指针指向的元素平方大res[i] nums[left] * nums[left];left;} else { // 右指针指向的元素平方大res[i] nums[right] * nums[right];right--;}}return res;
};这道题可以用双指针来解首先定义数组 res存放最终结果。然后定义两个指针 left 和 right分别指向数组的左端和右端。从后往前遍历数组每次比较左指针指向的元素平方值和右指针指向的元素平方值的大小将较大的值放入结果数组的末尾并将对应的指针移动到下一个位置。直到遍历完整个数组返回结果数组即可。
这样做的原因是因为当数组中的元素都为正数时平方后元素值会变大当数组中的元素都为负数时平方后元素值仍然变大但是由于数组是按非递减顺序排好序的因此无需再做一次排序操作。
该函数的时间复杂度是 O(n)其中 n 是数组的长度符合题目要求。 三数之和
题目内容
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例一
输入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] 。
注意输出的顺序和三元组的顺序并不重要。示例二
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例三
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。提示与限制
3 nums.length 3000。-105 nums[i] 105。
✅解答
初始提供代码
var threeSum function(nums) {};答案
var threeSum function(nums) {let res [];nums.sort((a, b) a - b); // 先对数组进行排序方便去重和缩小搜索范围let n nums.length;for (let i 0; i n; i) {if (nums[i] 0) { // 如果当前值大于0则三数之和一定大于0break;}if (i 0 nums[i] nums[i-1]) { // 去重如果当前值与前一个值相同则直接跳过continue;}let left i 1, right n - 1; // 定义双指针分别指向当前值的下一个数和数组的右端while (left right) { // 左右指针向中间靠近let sum nums[i] nums[left] nums[right]; // 计算当前三数之和if (sum 0) { // 如果满足条件将结果放入结果集中res.push([nums[i], nums[left], nums[right]]);while (left right nums[left] nums[left1]) { // 去重如果左指针指向的元素与下一个元素相同则向右移动指针left;}while (left right nums[right] nums[right-1]) { // 去重如果右指针指向的元素与前一个元素相同则向左移动指针right--;}left;right--;} else if (sum 0) { // 如果三数之和小于0则将左指针向右移动一位left;} else { // 如果三数之和大于0则将右指针向左移动一位right--;}}}return res;
};这题思路是先对数组进行排序然后将三数之和为 0 的组合找出来。外层循环遍历数组中的每一个数内层循环使用双指针来找出与当前数相加为 0 的另外两个数。找到之后将符合条件的组合放入结果集中。由于数组已经排序并且去重因此双指针搜索的范围会越来越小时间复杂度为 O(n^2)。
需要注意的是在查找三数之和为 0 的时候可以直接判断当前值是否大于 0如果是则说明后面的数不可能组成三数之和为 0因此直接退出循环即可。同时如果当前值与前一个值相同也可以直接跳过避免重复计算。
leetcode 示例代码
/*** param {number[]} nums* return {number[][]}*/
var threeSum function(nums) {let res [];if(nums.length 3){return res}if(nums.length 3){if(nums[0] nums[1] nums[2] 0) {res.push([nums[0],nums[1],nums[2]])return res}else{return res}}nums.sort((a, b) a - b);const len nums.length;for(let i 0;i nums.length;i){if(nums[i] 0) break;if(i 0 nums[i] nums[i-1]) continue;let L i 1;let R len - 1;while(L R) {const sum nums[i] nums[L] nums[R];if(sum 0){res.push([nums[i],nums[L],nums[R]]);while (L R nums[L] nums[L1]) L; while (L R nums[R] nums[R-1]) R--; L;R--;}else if (sum 0) L;else if (sum 0) R--;}}return res
};最后
感谢阅读到这这就是 Day3 的全部内容了这个系列暂时离开一会因为蓝桥云课接下来的题目都是要会员才能看因此后续内容将转战到 leetcode 的题目发布为标准那么这三天的数组内容也先告一段落了。文章内容中题目的答案都是通过检测的了如果有疑问和争议的内容可以评论区留言和私信我收到消息第一时间解答和回复。 点赞收藏防止迷路 ✅感谢观看下期再会 CSDN | 黛琳ghz
