leetCode之双指针遍历/滑动窗口

首页目录 点击查看

第一题

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

解题思路

  • 这道理我想了好久啊，都觉得没有很好地方式可以处理，看了一个大神的解题思路，我豁然开朗，贴出来
    使用一个数组来维护滑动窗口
    遍历字符串，判断字符是否在滑动窗口数组里不在则 push 进数组
    在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
    然后将 max 更新为当前最长子串的长度
    遍历完，返回 max 即可


    image.png

我的答案

根据以上思路，答案就很容易写出来了

        var lengthOfLongestSubstring = function (s) {
            let max = 0,
                array = [];
            for (let i = 0; i <= s.length - 1; i++) {
                let index = array.indexOf(s[i])
                if (index !== -1) {
                    array.splice(0, index + 1)
                }
                array.push(s[i])
                max = Math.max(array.length, max)
            }
            return max
        };
image.png
  • 时间复杂度：O(N)
  • 空间复杂度： O(N)

高分答案

除了以上的维护数组的方法，还有另外两种解题思路，维护下标以及优化map

//维护下标
var lengthOfLongestSubstring = function(s) {
    let index = 0, max = 0
    for(let i = 0, j = 0; j < s.length; j++) {
        index = s.substring(i, j).indexOf(s[j]) 
        if(index !== -1) { 
            i = i + index + 1 
        } 
        max = Math.max(max, j - i + 1) 
    }
    return max
};


//优化Map
var lengthOfLongestSubstring = function(s) {
    let map = new Map(), max = 0
    for(let i = 0, j = 0; j < s.length; j++) {
        if(map.has(s[j])) {
            i = Math.max(map.get(s[j]) + 1, i)
        }
        max = Math.max(max, j - i + 1)
        map.set(s[j], j)
    }
    return max
};

这两个的性能都差不多，稍微比我的第一种要好一点，在内存消耗上优势更加明显。


image.png

第二题

  • 难度：中等
  • 题目：11. 盛最多水的容器
    给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
    说明：你不能倾斜容器，且 n 的值至少为 2。
    image

    图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
    示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49

解题思路

  • 简单粗暴双循环，遍历数组，挨个去比较
  • 双指针 效率更高,定义两个角标i,j 根据数值的大小动态改变i,j的值，直到把数组数值都比较一遍。

我的答案

  • 简单粗暴双循环
            let area = 0,
                carea = 0;
            for (let i = 0; i <= height.length - 1; i++) {
                for (let j = i + 1; j <= height.length - 1; j++) {
                    carea = Math.min(height[i], height[j]) * (j - i)
                    if (area <= carea) {
                        area = carea
                    }
                }
            }
            return area

  • 时间复杂度：O(N2)

  • 空间复杂度： O(N)


    image.png

  • 双指针

            let area = 0,
                carea = 0,
                i = 0,
                j = height.length - 1;
            while (i < j) {
                carea = Math.min(height[i], height[j]) * (j - i)
                if (area <= carea) {
                    area = carea
                }
                if (height[i] < height[j]) {
                    i++
                } else {
                    j--
                }
            }
            return area
  • 时间复杂度：O(N)

  • 空间复杂度： O(N)


    image.png

    这两者的性能差距实在是太大了，所以还是推荐双指针吧。

第三题

  • 难度：中等
  • 题目： 15. 三数之和
    给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
    注意：答案中不可以包含重复的三元组。

示例

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

双指针的做法，首先对数组进行排序，如果第一个数大于零则直接返回空，遍历整个数组，如果当前的nums[i] ===nums[i + 1] 则直接continue，没必要浪费时间，设置left=i+1、right = nums.length-1 当left <right，判断nums[i] + nums[left] + nums[right]，如果和大于零，则减小right 反之增大left，如果相等，保存数值，也要判断left和right的上一位和下一位是否相等，如果相等则直接进行下一个。

我的答案

var threeSum = function (nums) {
    let array = []
    nums.sort((a, b) => {
        return a - b
    })
    if (nums[0] > 0) {
        return array
    }
    for (let i = 0; i <= nums.length - 1&& nums[i] <=0; i++) {
        let left = i + 1;
        let right = nums.length - 1
        if (nums[i] == nums[i - 1]) continue; // 去重
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right]
            if (sum < 0) {
                left++
            }
            if (sum > 0) {
                right--
            }
            if (sum === 0) {
                array.push([nums[left], nums[right], nums[i]])
                while (left < right && nums[left] == nums[left + 1]) left++; // 去重
                while (left < right && nums[right] == nums[right - 1]) right--; // 去重
                left++;
                right--
            }
        }
    }
    return array
};
image.png

第四题

  • 难度：中等
  • 题目： 16. 最接近的三数之和
    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
    示例
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

解题思路

  • 这道题的解题思路和之前的的三数之和很类似，相当于之前的相加等于0，现在改为任意数字，然后加一个判断是否和是和目标最接近的。

我的答案

            var threeSumClosest = function (nums, target) {
            let dis = null,
                result = 0;
            nums.sort((a, b) => {
                return a - b
            })
            for (let i = 0; i <= nums.length - 1; i++) {
                let left = i + 1;
                let right = nums.length - 1
                if (nums[i] == nums[i - 1]) continue; // 去重
                while (left < right) {
                    let sum = nums[i] + nums[left] + nums[right]
                    let current = Math.abs(target - sum)
                    if (dis > current) {
                        dis = current
                        result = sum
                    }
                    if (dis === null) {
                        dis = current
                        result = sum
                    }
                    if (sum > target) {
                        right--
                    }
                    if (sum < target) {
                        left++
                    }
                    if (sum - target === 0) {
                        return sum
                    }
                }
            }
            return result
        };
image.png

第五题

  • 难度：简单
  • 题目：26. 删除排序数组中的重复项
    给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
    不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
    示例：
给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

说明：
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

  • 裁剪数组
    这道题可以倒着遍历数组，创建一个last用于存放数组最后一个数，用当前遍历到的数和last对比，如果不等于last则把当前数赋值给last，否则说明两数相等，删除当前数值。
  • 双指针
    这里双指针的方法，和之前不太一样，right不是从最后一个数开始，而是从left下一位开始，比较两数大小，如果两者不相等，则将right的值赋值给left的下一位。

我的答案

  • 裁剪数组
        var removeDuplicates = function (nums) {
            let last = nums[nums.length] - 1;
            for (let i = nums.length - 1; i >= 0; i--) {
                if (nums[i] !== last) {
                    last = nums[i]
                } else {
                    nums.splice(i, 1)
                }
            }
            return nums.length
        };
        console.log(removeDuplicates([1, 1, 2, 2, 3, 3, 4, 5, 6]))
image.png
  • 双指针
        var removeDuplicates = function (nums) {
            let i = 0;
            let j = 1;
            while (j < nums.length) {
                if (nums[i] !== nums[j]) {
                    nums[++i] = nums[j]
                }
                j++
            }
            return i + 1
        };
        console.log(removeDuplicates([1, 1, 2, 2, 3, 3, 4, 5, 6]))
image.png

这两种方法比较极端啊，一个内存消耗低，一个执行时间短，各有所长，不过我更觉得双指针更好

第六题

  • 难度：中等
  • 题目：75. 颜色分类
    给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
    此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
    注意:
    不能使用代码库中的排序函数来解决这道题。

示例

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路

  • 这道题因为本来就属于双指针的题目，所以理所当然就使用双指针，只是这里，单纯的双指针明显是不够用的，所以这里需要添加一个current，表示当前的数值index。
  • 另外一个方法是看了题解，遇到0就删除该元素，放到最前面，遇到2就删除该元素，放到最后面，遇到1不处理

我的答案

  • 操作删除元素
        var sortColors = function (nums) {
            let index = 0;
            let count = 0;
            while (count < nums.length) {
                if (nums[index] === 0) {
                    nums.splice(index, 1)
                    nums.unshift(0)
                    index++
                } else if (nums[index] === 2) {
                    nums.splice(index, 1)
                    nums.push(2)
                } else {
                    index++
                }
                count++
            }
            return nums
        };
image.png
  • 双指针
        var sortColors = function (nums) {
            let left = 0;
            let right = nums.length - 1;
            let current = 0
            while (current <= right) {
                if (nums[current] === 0) {
                    [nums[current], nums[left]] = [nums[left], nums[current]];
                    left++
                    current++
                    continue;
                } else if (nums[current] === 2) {
                    [nums[current], nums[right]] = [nums[right], nums[current]];
                    right--
                    continue;
                } else {
                    current++
                    continue;
                }
            }
            return nums
        };
image.png

双指针的性能和直接操作元素的差距还是比较明显的。

第七题

  • 难度：中等
  • 题目：209. 长度最小的子数组
    给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解题思路

  • 这道题的解题思路就是滑动窗口，先扩大搜索范围，找到合适的区域，然后再缩小区域，找出最合适的解。

我的答案

var minSubArrayLen = function (s, nums) {
    let minLen = Infinity;
    let left = 0;
    let right = 0;
    let sum = 0;
    while (right < nums.length ) {
        sum += nums[right]
        while (sum >= s) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left]
            left++
        }
        right++
    }
    return minLen === Infinity ? 0 : minLen
};
image.png

第八题

  • 难度：中等
  • 题目：80. 删除排序数组中的重复项 II
    给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
    不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例

给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。
给定 nums = [0,0,1,1,1,1,2,3,3],
函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
你不需要考虑数组中超出新长度后面的元素。

为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

  • 这道题和 26. 删除排序数组中的重复项非常类似，只需要把+1改为+2就是答案，但是这个答案的效率看了一下并不是很高，所以看了一下题解，看到一个大哥的答案，觉得解题思路很厉害，贴出来

我的答案

  • 26题改
 var removeDuplicates = function (nums) {
            let index = 0;
            let pass = 0;
            while (index + pass <= nums.length - 1) {
                let current = nums[index + pass + 2];
                if (current === nums[index]) {
                    pass++
                } else {
                    index++;
                    [nums[index], nums[index + pass]] = [nums[index + pass], nums[index]]
                }
            }
            return index
        };
image.png
  • 空间O(1)
var removeDuplicates = function (nums) {
    let index = 0;
    for (let i = 0; i <= nums.length - 1; i++) {
        if (index < 2 || nums[i] > nums[index - 2]) {
            nums[index++] = nums[i];
        }
    }
    return index
};
image.png
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,911评论 5赞 460
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 82,014评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 142,129评论 0赞 320
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,283评论 1赞 264
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,159评论 4赞 357
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,161评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,565评论 3赞 382
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,251评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,531评论 1赞 292
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,619评论 2赞 310
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,383评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,255评论 3赞 313
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,624评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,916评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,199评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,553评论 2赞 342
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,756评论 2赞 335