首页目录点击查看

第一题

难度：中等
题目：3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例

输入: "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

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

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

首页目录点击查看

第一题

解题思路

我的答案

高分答案

第二题

解题思路

我的答案

第三题

示例

解题思路

我的答案

第四题

解题思路

我的答案

第五题

解题思路

我的答案

第六题

示例

解题思路

我的答案

第七题

示例

解题思路

我的答案

第八题

示例

解题思路

我的答案

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

首页目录 点击查看

第一题

解题思路

我的答案

高分答案

第二题

解题思路

我的答案

第三题

示例

解题思路

我的答案

第四题

解题思路

我的答案

第五题

解题思路

我的答案

第六题

示例

解题思路

我的答案

第七题

示例

解题思路

我的答案

第八题

示例

解题思路

我的答案

首页目录点击查看