目录
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
1. 创建一个map,for循环遍历nums数组
2. 用target减nums[i](以计算哪个数跟当前的数字相加得到target)
3. 检查map里有没有这个数(如果有则返回结果,如果没有把nums[i]当做key,i当做value放入map中)
4. map.has()检查map中有没有当前key
- /**
- * @param {number[]} nums
- * @param {number} target
- * @return {number[]}
- */
- var twoSum = function(nums, target) {
- const map =new Map();
- for(let i=0;i
length;i++){ - const num=target-nums[i]
- if(map.has(num)){
- return[map.get(num),i]
- }else{
- map.set(nums[i],i)
- }
- }
- return []
- };
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
创建一个set
两个指针,第一个指针指向字符串开头(j)。第二个随着for循环遍历字符串(i)
如果set里没有s[i],说明目前为止还没有重复的字符串把s[i]添加到set里面,更新最大不重复字符的数量
如果set里面有s[i]则从set里面删除s[j],并且递增,在检查set里面有没有s[i]
如此反复直到set里面没有s[i]为止,直到遍历完整个数组
滑动窗口算法
什么是滑动窗口?
其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!
如何移动?
我们只要把队列的左边的元素移出就行了,直到满足题目要求!
- /**
- * @param {string} s
- * @return {number}
- */
- var lengthOfLongestSubstring = function(s) {
- const set=new Set()
- let i=0,j=0,maxlen=0;
- if(s.length=0){
- return 0
- }
- for(i;i
- if(!set.has(s[i])){
- set.add(s[i])
- maxlen=Math.max(maxlen,set.size)
- }else{
- while(set.has(s[i])){
- set.delete(s[j])
- j++
- }
- set.add(s[i])
- }
- }
- return maxlen
- };
最长回文子串
你一个字符串 s
,找到 s
中最长的回文子串。
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
1. 如果字符串长度小于2,直接返回原字符串
2. 定义两个变量start存储当前找到的最大回文字符串的起始位置,另一个maxlen记录字符串的长度(终止位置就是start+mexlen)mexlen=1(ab)
3. 创建一个helper function 判断左边和右边是否越界,同时最左边的字符等于最右边的字符,如果三个条件都满足,则判断是否需要更新回文字符串最大长度,然后left--,right++,继续判断,直到不满足三个条件之一
4. 遍历字符串,每个位置调用helper function两遍 第一遍 i-1,i+1(babad有中心点)第二遍i,i+1(cabbad没有中心点)
- /**
- * @param {string} s
- * @return {string}
- */
- var longestPalindrome = function(s) {
- // 字符串小于2,返回该字符串
- if(s.length<2){
- return s
- }
- // 起始位置,和最大长度 最大长度默认应该为1(ab 最大回文应该是1)
- let start=0,maxlen=1;
- function expandAroundCenter(left,right){
- //判断左边右边是否越界,同时左边字符等于右边字符
- while(left>=0&&right
length&&s[left]===s[right]){ - //判断是否需要更新回文字符串最大长度
- if(right-left+1>maxlen){
- maxlen=right-left+1
- start=left
- }
- left--;
- right++;
- }
- }
- for(let i=0;i
length;i++){ - expandAroundCenter(i-1,i+1)
- expandAroundCenter(i,i+1)
- }
- return s.substring(start,start+maxlen)
- };
三数之和
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
1. 给数组排序
2. 遍历数组,从0遍历到length-2(防止越界)
3. 如果当前的数字,等于前一个数字则跳过这个数(避免重复项)
4. 如果数字不同,则设置start=i+1,end=length-1,查看i start end 三个数的和比0大还是小,如果比0小start++,比0大end--,如果等于0把三个数加到结果里面
5. 返回结果
- /**
- * @param {number[]} nums
- * @return {number[][]}
- */
- var threeSum = function(nums) {
- let result=[]
- nums.sort(function(a,b){
- return a-b
- })
- //防止越界
- for(let i=0;i
length-2;i++){ - //如果是第一个元素,或者两个数相等就不需要比较
- if(i===0||nums[i]!==nums[i-1]){
- let start=i+1,
- end=nums.length-1;
- //两个数碰面之后结束循环
- while(start
- //如果相等返回数组
- if(nums[i]+nums[start]+nums[end]===0){
- //移动的时候记得去重
- result.push([nums[i], nums[start], nums[end]])
- start++
- end--
- // start跟前一个比如果想同继续向后缩进
- while(start
1]){ - start++
- }
- // end 跟后一个比较,如果相等继续向前缩进
- while(start
1]){ - end--
- }
- //小于0 start++
- }else if(nums[i]+nums[start]+nums[end]<0){
- start++
- }else{// 大于0end--
- end--
- }
- }
- }
- }
- return result
- };
加一
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
输入:digits = [1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。
1. 倒序循环数组
2. 如果当前项不等于9直接加1位返回数组
3. 如果是9把当前项改为0继续循环
4. 如果都等于0拼上1
- /**
- * @param {number[]} digits
- * @return {number[]}
- */
- var plusOne = function(digits) {
- for(let i=digits.length-1;i>=0;i--){
- if(digits[i]!==9){
- digits[i]++
- return digits
- }else{
- digits[i]=0
- }
- }
- const result=[1,...digits]
- return result
- };
存在重复元素
给你一个整数数组 nums
。如果任一值在数组中出现 至少两次 ,返回 true
;如果数组中每个元素互不相同,返回 false
。
输入:nums = [1,2,3,1]
输出:true
创建set结构
循环数组判断set中有没有这个值 有返回true
没有add追加 循环结束没有返回 则为false
- /**
- * @param {number[]} nums
- * @return {boolean}
- */
- var containsDuplicate = function(nums) {
- let set =new Set()
- for(let i=0;i
length;i++){ - if(set.has(nums[i])){
- return true
- }else{
- set.add(nums[i])
- }
- }
- return false
- };
移动0
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
声明一个指针j
循环数组 i 如果不等于移动到 j 的位置 j++
循环结束 把剩余位置补0
- /**
- * @param {number[]} nums
- * @return {void} Do not return anything, modify nums in-place instead.
- */
- var moveZeroes = function(nums) {
- let j = 0;
-
- for (let i = 0; i < nums.length; i++) {
- if (nums[i] != 0) {
- nums[j] = nums[i];
- j++;
- }
- }
-
- for (i = j; i < nums.length; i++) {
- nums[i] = 0
- }
-
- return nums
- };
两个数组的交集
给定两个数组 nums1
和 nums2
,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
创建set 结构 因为没有重复项
循环数组1 includes检测数组2中是否包含1的内容 包含add追加
array.from转为数组
- /**
- * @param {number[]} nums1
- * @param {number[]} nums2
- * @return {number[]}
- */
- var intersection = function(nums1, nums2) {
- let set =new Set()
- for(let i=0;i
length;i++){ - if( nums2.includes(nums1[i])){
- set.add(nums1[i])
- }
- }
- return Array.from(set)
- };
-
相关阅读:
47. UE5 RPG 实现角色死亡效果
集线器与交换机、虚拟局域网(3.3)
1 动态规划
Spring 6【数据绑定时类型转换、装饰器设计模式、DataBinder源码分析BeanWrapper、Errors、BindingResult】(十二)-全面详解(学习总结---从入门到深化)
有一门课不及格的学生
leetcode刷题 二维数组 八方向
GLPI资产管理系统安装Fusioninventory插件发现Windows和Linux主机
全球十大即时通信软件最新排名
基于Softmax回归的多分类任务
Linux- 命名信号量和无名信号量的区别
-
原文地址:https://blog.csdn.net/qq_63358859/article/details/126003822