LeetCode10 - 和为 K 的子数组
📝 题目描述 题目链接：和为 K 的子数组 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例： 1234567891011示例 1：输入：nums = [1,1,1], k = 2输出：2示例 2：输入：nums = [1,2,3], k = 3输出：2 提示： 1 <= nums.length <= 2 * 10^4 -1000 <= nums[i] <= 1000 -10^7 <= k <= 10^7 💡 解题思路 方法一：暴力解法 最容易想到的朴素解法，使用一个二重循环，列举出所有可能的开头i和结尾j，然后计算它们代表的子数组的和，在计算和时，由于我们的内层循环（代表结尾的j）是逐个往后列举的，因此可以令sum += nums[j]而不必重新遍历来计算和，稍微降低了一下复杂度。 方法二：前缀和 + 哈希表优化 方法一中，对于每个开头i，我们要遍历i后的每一个元素来找结尾j。 对于这种：知道最终和k，知道其中一个元素i，求另一个元素j的问题，...
LeetCode9 - 找到字符串中所有字母异位词
📝 题目描述 题目链接：找到字符串中所有字母异位词 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。 示例： 123456789101112131415161718示例 1:输入: s = "cbaebabacd", p = "abc"输出: [0,6]解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。 示例 2:输入: s = "abab", p = "ab"输出: [0,1,2]解释:起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。起始索引等于 1 的子串是 "ba", 它是 "ab...
LeetCode8 - 无重复字符的最长子串
📝 题目描述 题目链接：无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。 示例： 1234567891011121314151617181920示例 1:输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。示例 2:输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 提示： 0 <= s.length <= 5 * 10^4 s 由英文字母、数字、符号和空格组成 💡 解题思路 方法一：...
LeetCode7 - 接雨水
📝 题目描述 题目链接：接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例： 123456789101112示例 1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2：输入：height = [4,2,0,3,2,5]输出：9 提示： n == height.length 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5 💡 解题思路 方法一：动态规划 我们先考虑一般情况，特殊情况我们最后再考虑。 ①一般情况： 比如，对于上图中的横坐标为2的位置，它在垂直方向能接多少雨水呢？ 我们可以得到对于每个横坐标位置，接雨水的量 = 该位置雨水可以淹没多高 - 该位置的高度; 很明显该位置的高度就是height[2] = 1，那么怎么算该位置可以雨水可以淹没多高呢？ 这有点...
LeetCode6 - 三数之和
📝 题目描述 题目链接：三数之和 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意： 答案中不可以包含重复的三元组。 示例： 123456789101112131415161718192021222324示例 1：输入：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] 。注意，输出的顺序和三元组的顺序并不重要。示例 2：输入：nums = [0,1,1...
LeetCode5 - 盛最多水的容器
📝 题目描述 题目链接：盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明： 你不能倾斜容器。 示例： 12345678910111213示例 1：输入：[1,8,6,2,5,4,8,3,7]输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = [1,1]输出：1 提示： n == height.length 2 <= n <= 10^5 0 <= height[i] <= 10^4 💡 解题思路 方法一：双指针 难点在于如何想到初始时让左右指针分别处于两端，然后不断让左右指针中，高度较小的那个往中间移动。 假设初始时，左指针和右指针指向的数分别为 LLL 和 RRR，假设 L≤RL≤RL≤R。同时，两个指针之间的距...
LeetCode4 - 移动零
📝 题目描述 题目链接：移动零 给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。 请注意，必须在不复制数组的情况下原地对数组进行操作。 示例： 12345678910示例 1:输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]示例 2:输入: nums = [0]输出: [0] 提示： 1 <= nums.length <= 10^4 -2^31 <= nums[i] <= 2^31 - 1 💡 解题思路 方法一：暴力解法 遍历数组（ptr1），每当遇到一个0时，就停下来。然后启动一个内层循环（ptr2），从当前位置向后扫描，寻找第一个非零元素。找到后，将两者交换，保证非零元素被挪到前面，0被挪到后面。 缺点： 被动地“填坑”，发现一个0，赶紧去找个数来填上。 方法二：快慢指针解法✅️ 使用两个指针， left（慢指针）： 维护非零数组的边界，含义是“下一个非零元素应该放置的位置”。 right（快指针）： 负责在前探路，遍历整个数组。 当right遇到非零数，就把它和left位置...
LeetCode 3 - 最长连续序列
📝 题目描述 题目链接：最长连续序列 给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为O(n)O(n)O(n)的算法解决此问题。 示例： 123456789101112131415示例 1：输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：输入：nums = [0,3,7,2,5,8,4,6,0,1]输出：9示例 3：输入：nums = [1,0,1,2]输出：3 提示： 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 💡 解题思路 方法一：哈希表 首先是暴力解法，对于数组中的每一个元素n，以n作为起点，不断匹配n+1是否存在、n+2是否存在，直到n+x是否存在，假设最多匹配到n+x，那么此序列长度就是x+1。 优化1：对于匹配的过程，我们可以提前将所有元素放入哈希表，这样查看一个元素是否存在的复杂度就从O(n)O(n)O(n)降低至...
LeetCode 2 - 字母异位词分组
📝 题目描述 题目链接：字母异位词分组 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。 示例： 123456789101112131415161718192021222324示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]]解释：- 在 strs 中没有字符串可以通过重新排列来形成 "bat"。- 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。- 字符串 "...
LeetCode 1 - 两数之和
📝 题目描述 题目链接：两数之和 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。 示例： 12345678910111213141516示例 1：输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：输入：nums = [3,2,4], target = 6输出：[1,2]示例 3：输入：nums = [3,3], target = 6输出：[0,1] 提示： 2 <= nums.length <= 10^4 -10^9 <= nums[i] <= 10^9 -10^9 <= target <= 10^9 只会存在一个有效答案 💡 解题思路 方法一：暴力解法 最直接的方法是暴力枚举，即枚举数组中的每一个数x，寻找数组中是否存在target -...