首页目录 点击查看

第一题

• 难度：中等
• 题目：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