一、思路 分治：将问题拆解为两数之和加第三个数和第四个数 二、问题 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 注意： 答案中不可以包含重复的四元组。 示例： 给定数组…

一、思路 分治：将问题拆解为两数之和加第三个数 二、问题 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。   示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1…

一、思路 利用哈希表优化O(n)复杂度的查找，这是工作中常见优化点。 二、问题 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。   示例 1： 输入：nums =…

一、思路 与前两道打家取舍相比，结合了二叉树。 选择变成了，偷当前节点，下一步就去偷孙子节点。不偷当前节点，就去偷儿子节点。两个选择一计算，看哪个状态更优。 这儿还得注意动态规划常见的重叠子问题，用哈希表来优化。 二、问题 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根&rd…

一、思路 相比打家取舍一，不能同时偷第一家和最后家。就是多了个选择，要不偷第一家，要不偷最后家。 动态规划问题就是要在题目中找出选择，得出状态。 二、问题 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相…

一、思路 这是典型的动态规划问题。要想得到最优策略，就得在每个选择时刻最出最优决策。选择产生状态，合并状态得到结果。 开始认为，求最优选择时，只计算某一个选择。导致不知道怎么得出某一个。后来发现，应该把所有选择都计算，得到多个状态，取最优的状态。 二、问题 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就…

一、思路 这题也是滑动窗口类型，判断窗口内是否有重复值时，我使用的是集合+队列。集合判断是否重复，队列记录窗口位置。解题后看了下题解，才发现滑动窗口类型确实做少了，这题明明可以用通用解法：下标+map，下标记录窗口位置，map判断是否重复（泛型为<字符，出现的次数>）。 用集合+队列还有个坑：当窗口从未缩小时，是没有触发计算length，需要…

一、思路 这题虽然也是滑动窗口，但是是属于比较“死板”的滑动窗口，因为它的窗口是固定的，所以有相对简单的解法。我将两种解法都写出来了（简单解法和滑动窗口一般解法）。 二、题目 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超…

一、思路 熟悉下滑动窗口算法，虽然能理解，但细节问题还是遇到很多。调试了很多遍才通过。 最后个用例过不了，用例长度特别大，当时只想到是不是Integer溢出，但是又没报错。那个用例大得都复制不了，无赖只能看题解。 原来是Integer比较时用了==，前面的用例为啥通过了？因为Integer缓存[-128-127]。 二、题目 给你一个字符串 s 、…

一、思路 这是最基本的二分，easy！ 说一下这里：int mid = left + ((right - left) >> 1); 1、移位是为了提高效率 2、不用(left+right)/2是防止int溢出 二、题目 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target &nbs…