力扣爆刷第84天之hot100五连刷6-10

力扣爆刷第84天之hot100五连刷6-10

文章目录

• • • 力扣爆刷第84天之hot100五连刷6-10
    • 一、15. 三数之和
    • 二、42. 接雨水
    • 三、3. 无重复字符的最长子串
    • 四、438. 找到字符串中所有字母异位词
    • 五、560. 和为 K ���子数组

      一、15. 三数之和

      题目链接：https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked

      （）

      思路：三数之和和两数之和类似都是使用双指针进行操作，只不过nums数组内包含重复元素，需要考虑去重的操作，先排序，然后外层一个for内层双指针即可完成遍历，完成去重有两步。

      一步： if (i > 0 && nums[i] == nums[i-1]) continue;杜绝相同的nums[i]。

      （）

      二步：当nums[j]+nums[k]==nums[i]时，务必保证nums[j]和nums[k]不再重复。

      while(j  
      class Solution {    public List threeSum(int[] nums) {        List array = new ArrayList();        Arrays.sort(nums);        int len = nums.length;        for(int i = 0; i  0) break;            if (i > 0 && nums[i] == nums[i-1]) continue;            int j = i+1, k = len-1;            while(j  
      二、42. 接雨水
       
      题目链接：https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
      思路：接雨水是典型的单调栈问题，只需要构造出来凹型即可，也就是栈内，自栈底到栈顶是递减的，当遇到大于栈顶的元素时，就弹出栈顶，此时栈顶即为凹槽，然后计算面积即可。
       
      class Solution {   public int trap(int[] height) {       Deque stack = new LinkedList();       int sum = 0;       for(int i = 0; i  
      三、3. 无重复字符的最长子串
       
      题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked
      思路：如s = “abcabcbb” 长度为3，典型的滑动窗口，使用set维护不重复的子串，每次新加入元素后，更新最大长度，如果遇到重复元素，则开始缩小窗口，直到当前元素不重复，才继续开始扩大窗口。
       
      class Solution {  public int lengthOfLongestSubstring(String s) {        int max = 0;        Set set = new HashSet();        int slow = 0;        for(int i = 0; i  
      四、438. 找到字符串中所有字母异位词
       
      题目链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
      思路：一看是异位词基本上就得使用set或map来处理，字符串的长度又巨长，10的4次方，常规遍历自然超时，需要使用双指针去掉一层循环，即使用滑动窗口，维护好字符串窗口，开始时扩大窗口，顺便记录标记值，当窗口达到p字符串长度时，进行判断，看看标记值是否符合，然后缩减窗口，这样一次循环结束。
      滑动窗口模板：
       
      /* 滑动窗口算法框架 */void slidingWindow(String s) {    // 用合适的数据结构记录窗口中的数据    HashMap window = new HashMap();    int left = 0, right = 0;    while (right  
      题解：
       
      class Solution {    public List findAnagrams(String s, String p) {        List list = new ArrayList();        int sLen = s.length(), pLen = p.length();        if(pLen > sLen) return list;        Map need = new HashMap();        Map window = new HashMap();        for(char c : p.toCharArray()) {            need.put(c, need.getOrDefault(c, 0)+1);        }        int left = 0, right = 0, valid = 0;        while(right  
      五、560. 和为 K 的子数组
       
      题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
      思路：求和为k的子数组，其实就是前缀和，和使用前缀和数组的题目有点像，但是为了少一层for，把原本要存入前缀和数组的值，都存进了hashmap，然后只需要用preSum - k 去map中寻找value即可。
       
      class Solution {    public int subarraySum(int[] nums, int k) {        Map map = new HashMap();        map.put(0, 1);        int count = 0, preSum = 0;        for(int i = 0; i