Leetcode刷题记录1 哈希+双指针+滑动窗口

标签：nums int res height 哈希 new left Leetcode 刷题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
hot100
总结

前言

记录一些leetcode刷题中遇到的问题，共勉

hot100

1.哈希

#1.两数之和

题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

方法一：暴力法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }

}

暴力枚举两个数的下标位置

方法二：哈希

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 元素不重复，使用
        // (key,value):(元素，元素下标)
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        for(int i=0;i<n;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return null;

    }

}

#49.字母异位词分组

题目：给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

方法一：哈希表，先计算每个字符串中对应的字符个数，再将字符个数相等的字符串存入对应list中

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int len = strs.length;
        int[][] alphabet = new int[len][26];
        // 统计出每个字符串中对应的字符个数
        for(int i=0;i<len;i++){
            String s = strs[i];
            int lenS = s.length();
            for(int j=0;j<lenS;j++){
                alphabet[i][s.charAt(j)-'a']++;
            }
        }

        // 判断是否已经放入list中
        boolean[] used = new boolean[len];

        List<List<String>> res = new ArrayList<>();
        List<String> list;
        // 遍历字符串数组,将所有对应字符相等的字符串，即字母异位词放在同一个list中
        for(int i=0;i<len;i++){
            if(used[i]==false){
                list = new ArrayList<>();
                list.add(strs[i]);
                used[i] = true;
            }
            else{
                continue;
            }      
            for(int j=i+1;j<len;j++){
                if(judgeIsAnagrams(alphabet,i,j)){
                    list.add(strs[j]);
                    used[j] = true;
                }
            }
            res.add(new ArrayList<>(list));
            
        }

        return res;
    }

    public boolean judgeIsAnagrams(int[][] alphabet, int index1, int index2){
        for(int i=0;i<26;i++){
            if(alphabet[index1][i]!=alphabet[index2][i]){
                return false;
            }
        }
        return true;
    }
}

方法二：先按照字母表顺序拼接出各个字母异位词的字符串，再将字符串以及对应存储字符串的列表存入哈希表中

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int len = strs.length;
        int[][] alphabet = new int[len][26];
        // 统计出每个字符串中对应的字符个数
        for (int i = 0; i < len; i++) {
            String s = strs[i];
            int lenS = s.length();
            for (int j = 0; j < lenS; j++) {
                alphabet[i][s.charAt(j) - 'a']++;
            }
        }

        Map<String, List<String>> map = new HashMap<>();

        for (int i = 0; i < len; i++) {
            // alphabet[i][26]
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 26; j++) {
                int temp = alphabet[i][j];
                char c = (char) (j + 'a');
                while (temp-- > 0) {
                    sb.append(c);
                }

            }
            String s = sb.toString();
            // System.out.println("s:"+s+",s.val"+s.hashCode());
            // Java 的字符串常量池机制
            // 如果每次StringBuilder对象中的内容都是相同的，那么在理想情况下它应该只创建一个字符串
            if (map.containsKey(s)) {
                map.get(s).add(strs[i]);
            } else {
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                map.put(s, list);
            }
        }

        List<List<String>> res = new ArrayList<>();

        for (List<String> value : map.values()) {
            res.add(value);
        }

        return res;

    }
}

#128.最长连续序列

题目：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

方法一：排序后进行累加，若不连续，则计数器count归1，重新从下一个数开始累计，这个思路容易想到，二分排序算法时间复杂度O(nlogn)

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        Arrays.sort(nums);
        int n = nums.length;
        int count=1;
        int res = 1;
        for(int i=0;i<n;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            
            if(i>0&&nums[i]==nums[i-1]+1){
                count++;
                res = Math.max(res,count);
            }
            else{
                count = 1;
            }
        }

        return res;
    }
}

方法二：借助哈希表来进行判断，快速判断一个数的下一个连续的数是否在数组中出现，跟方法一其实差不多

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        Arrays.sort(nums);
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        int n = nums.length;
        int count = 1;
        int res = 1;
        for(int i=0;i<n;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            if(set.contains(nums[i]+1)){
                count++;
                res = Math.max(res,count);
            }
            else{
                count = 1;
            }
        }
        return res;
    }
}

上面两个时间复杂度都没有达到要求，补充一个借鉴的思路
方法三：将数组元素添加进哈希表，之后从一个数开始，若存在与该数有关的连续数组，先找到比它小的最后一个数，从最后一个数开始计数，找到连续的最大长度

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }

        int maxLength = 0;

        for (int num : set) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;

                while (set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentLength += 1;
                }

                maxLength = Math.max(maxLength, currentLength);
            }
        }

        return maxLength;
    }
}

方法三力扣官方题解时间复杂度分析：link

2.双指针

#283.移动零

题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

方法一：暴力法，每次遍历遇到0，则将0交换到数组的末尾位置，同时0的计数器+1，遍历元素的个数-1，将其余元素依次往前移动一位

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int zeros = 0;
        for (int i = 0; i < n - zeros; i++) {
            if(nums[i]==0){
                for(int j=i;j<n-1-zeros;j++){
                    nums[j] = nums[j+1];
                }
                nums[n-1-zeros] = 0;
                zeros++;
                i--;
            }
        }
    }
}

方法二：双指针法

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int slow = 0;
        // slow为写指针，fast为读指针
        for (int fast=0;fast<n;fast++) {
            if(nums[fast]!=0){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        //将非零数前移后，一共有slow个非零数，slow指向第一个为0的位置（若存在），往后面的n-slow个数补0
        for(int i=slow;i<n;i++){
            nums[i] = 0;
        }

    }
}

#11.盛最多水的容器

题目：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

方法一：容易想到的思路是暴力枚举两条垂线的位置，不过超时了

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int res = 0;
        int sum = 0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                sum = Math.min(height[i],height[j])*(j-i);
                res = Math.max(res,sum);
            }

        }
        return res;
    }
}

方法二：双指针法

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int l = 0,r = n-1;
        int res = 0;
        while(l<=r){
            res = Math.max(res,Math.min(height[l],height[r])*(r-l));
            // 贪心 局部最优->全局最优
            // 当前height[l]<=height[r]时，将左指针向内移动 s = min(height[l],height[r])*(r-l) 
            // 向内移动，(r-l)减小，假设移动l，则min(height[l],height[r])可能增大或减小或不变，s同
            //                     假设移动r，则min(height[l],height[r])减小或不变，s一定减小
            //                     即只有移动l才可能使得s变得更大
            // 向外移动，(r-l)增大，假设移动l，则min(height[l],height[r])减小或增大或不变，s同
            //                     假设移动r，则min(height[l],height[r])减小或不变，s可能不变或增大或减小
            // 由于l与r都由向内移动转移而来，之间处于外圈时res中已经记录最大值，故无需再考虑向外移动的情况
            if(height[l]<=height[r]){
                l++;
            }
            else{
                r--;
            }
        }
        return res;
    }
}

#15.三数之和

题目：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //  去重之前先排序
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();

        int n = nums.length;
        int sum = 0;

        for(int i=0;i<n;i++){
            if(nums[0]>0){
                break;
            }

            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }

            int left = i+1;
            int right = n-1;
            while(left<right){
                sum = nums[i]+nums[left]+nums[right];
                if(sum==0){
                    // 先记录，再去重，否则后面去重完，若出现[0,0,0]这样的情况，三元组凑不够
                    List<Integer> list = new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right]));
                    res.add(new ArrayList<>(list));
                    while(left<right&&nums[i]+nums[left]+nums[right]==0&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left<right&&nums[i]+nums[left]+nums[right]==0&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
                else if(sum>0){
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return res;


    }
}

需要注意的一个地方是“if(i>0&&nums[i]==nums[i-1]){continue;}”，这个条件表示假设有多个重复的数时候，只取第一个数，算是一种去重的小技巧。

#42.接雨水

题目：给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

方法一：暴力枚举，按列计算，依次计算每根柱子的位置能接的雨水，步骤为找到该柱子左侧的最大值以及右侧的最大值，取二者中小的一个减去当前柱子高度即得到所能接雨水的值，累加即可


class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int area = 0;
        for(int i=1;i<n-1;i++){
            int leftMaxHeight = height[i];
            for(int j=i-1;j>=0;j--){
                if(leftMaxHeight<height[j]){
                    leftMaxHeight = height[j];
                }
            }
            int rightMaxHeight = height[i];
            for(int j = i+1;j<n;j++){
                if(rightMaxHeight<height[j]){
                    rightMaxHeight = height[j];
                }
            }
            area += Math.min(leftMaxHeight,rightMaxHeight)-height[i];    
        }
        return area;
    }
}

方法二：对方法一做了一些优化，因为判断左侧（右侧）柱子的最大值没必要每次都一直判断到最左侧（最右侧），可以用一个变量来记录当前柱子左侧（右侧）的最大值，之后每次判断当前柱子高度和该柱子左侧（右侧）的变量记录的值即可

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int area = 0;
        // leftMaxHeight[i]表示height[i]左侧，包括i的height最大值
        // rightMaxHeight[i]表示height[i]右侧，包括i的height最大值
        int[] leftMaxHeight = new int[n];
        int[] rightMaxHeight = new int[n];
        leftMaxHeight[0] = height[0];
        rightMaxHeight[n-1] = height[n-1];
       
        for(int i=1;i<n;i++){
            leftMaxHeight[i] = height[i];
            if(leftMaxHeight[i-1]>height[i]){
                leftMaxHeight[i] = leftMaxHeight[i-1];
            }
        }
        for(int i=n-2;i>=0;i--){
            rightMaxHeight[i] = height[i];
            if(rightMaxHeight[i+1]>height[i]){
                rightMaxHeight[i] = rightMaxHeight[i+1];
            }
        }
        for(int i=1;i<n-1;i++){
            area += Math.min(leftMaxHeight[i],rightMaxHeight[i])-height[i];
        }
        return area;
    }
}

方法三：按行计算，使用单调递增栈，可利用单调递增栈的性质（栈顶到栈底元素单调递增），来找到当前数组中第一个比栈顶元素大的元素。若当前数组的元素比栈元素大，由于栈中元素值单调递增的，之后取出栈顶元素作为中间的基底高度，弹栈之后再次取栈顶元素作为基底左边的高度，当前数组中第一个比栈顶元素大的元素作为基底右边的高度，便可计算当前行能接的雨水，之后再将该元素压入栈中；若当前数组的元素小于或等于栈顶元素，则将其压栈，注意，等于时候可以先弹栈，再压栈，因为此时能接的雨水为0，减少不必要的计算。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int area = 0;
        int res=0;
        // 存放索引号
        Stack<Integer> stack  = new Stack<>();
        stack.push(0);
        // 单调递增栈 栈顶到栈底单调递增
        // 按行计算
        for(int i=1;i<n;i++){
            if(height[stack.peek()]>height[i]){
                stack.push(i);
            }
            else if(height[stack.peek()]==height[i]){
                stack.pop();
                stack.push(i);
            }
            else{
                while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
                    int mid = stack.pop();
                    if(!stack.isEmpty()){
                        int left = stack.peek();
                        int w = i-left-1;
                        int h = Math.min(height[left],height[i])-height[mid];
                        area = w*h;
                        res += area;
                    }
                }
                stack.push(i);
            }
        }
        return res;
    }
}

方法四：按列计算，双指针，根据方法一、二可联想到，分别使用两个变量来记录当前元素的左边最大值，以及当前元素的右边最大值，由木桶可知，木桶能接水量的最大值取决于最大的木板，此时不管是左侧最大值大还是右侧最大值大，只要左右两侧都存在比当前元素大的元素，当前位置即能接到雨水，接到雨水的量取决于二者中小的那一个高度，减去当前元素高度

class Solution {
    public int trap(int[] height) {
        // 双指针
        // 按列计算
        int n = height.length;
        int res=0;
        int leftMax = 0;
        int rightMax = n-1;
        int left = 1;
        int right = n-2;
        
        while(left<=right){
            if(height[leftMax]<height[rightMax]){
                if(height[left]<height[leftMax]){
                    res += height[leftMax]-height[left];
                    left++;
                }
                else{
                	// 接不到雨水，left右移，更新leftMax
                    leftMax = left;
                    left++;
                }
            }
            else{
                if(height[right]<height[rightMax]){
                    res += height[rightMax]-height[right];
                    right--;
                }
                else{
                	// 接不到雨水，right左移，更新rightMax
                    rightMax = right;
                    right--;
                }

            }
        }
        return res;
    }
}

3.滑动窗口

#3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

方法一：暴力枚举

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int len = s.length();
        int count = 0;
        int res = 0;
        for(int i=0;i<len;i++){
            Set<Character> set = new HashSet<>();
            for(int j=i;j<len;j++){
                if(set.contains(chars[j])){
                    break;
                }
                set.add(chars[j]);
                count++;
            }
            res = Math.max(res,count);
            count = 0;
        }
        return res;
    }
}

方法二：滑动窗口法，从初始位置开始滑动，当遇到重复字符时候进行回退，回退到具有重复字符的下一个位置，即map.get(chars[i])+1位置处，开始写出的程序为注释掉的left语句，后面遇到测试用例"abba"，发现回退时候会回退到第一个字符’b’的位置，从而取得最大值为3，显然与题意不符合，故加以限制条件
left = Math.max(left,map.get(chars[i])+1);
使其不会跳回到之前的状态

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        char[] chars = s.toCharArray();
        int res = 0;
        Map<Character,Integer> map = new HashMap<>();
        int left = 0;
        for(int i=0;i<len;i++){
            if(map.containsKey(chars[i])){
                // left = map.get(chars[i])+1;
                left = Math.max(left,map.get(chars[i])+1);
            }
            map.put(chars[i],i);
            res = Math.max(res,i-left+1);
        }
        return res;

    }
}

#438. 找到字符串中所有字母异位词

题目：给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

方法一：哈希表+暴力枚举

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] chars = s.toCharArray();
        int lenS = s.length();
        int lenP = p.length();
        List<Integer> res = new ArrayList<>();
        int[] alphabetP = new int[26];
        for(char c:p.toCharArray()){
            alphabetP[c-'a']++;
        }
        for(int i=0;i<lenS;i++){       
            int[] alphabetS = new int[26];
            // 注意限制条件count<lenS，否则数组会越界
            for(int count=i;count<i+lenP&&count<lenS;count++){
                alphabetS[chars[count]-'a']++;
            }
            if(judgeIsCorresponding(alphabetP,alphabetS)){
                res.add(i);
            }      
        }
        return res;
    }

    public boolean judgeIsCorresponding(int[] alphabetP, int[] alphabetS){
        for(int i=0;i<26;i++){
            if(alphabetP[i]!=alphabetS[i]){
                return false;
            }
        }
        return true;
    }
}

方法二：方法一可以进行优化，没必要每次新创建一个哈希表来重新统计修剪之后的字符串s中的各个字符个数，可以采用滑动窗口法，一次滑出上一轮中的第一个元素，并加入这一轮中的新元素

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] chars = s.toCharArray();
        int lenS = s.length();
        int lenP = p.length();
        List<Integer> res = new ArrayList<>();
        int[] alphabetP = new int[26];
        for (char c : p.toCharArray()) {
            alphabetP[c - 'a']++;
        }
        int[] alphabetS = new int[26];
        for (int count = 0; count < lenP && count < lenS; count++) {
            alphabetS[chars[count] - 'a']++;
        }
        if (judgeIsCorresponding(alphabetP, alphabetS)) {
            res.add(0);
        }
        for (int i = lenP; i < lenS; i++) {
            //移除上一轮次的第一个元素
            alphabetS[chars[i-lenP]-'a']--;
            // 添加新元素
            alphabetS[chars[i]-'a']++;
            if (judgeIsCorresponding(alphabetP, alphabetS)) {
                res.add(i-lenP+1);
            }
        }
        return res;

    }

    public boolean judgeIsCorresponding(int[] alphabetP, int[] alphabetS) {
        for (int i = 0; i < 26; i++) {
            if (alphabetP[i] != alphabetS[i]) {
                return false;
            }
        }
        return true;
    }
}

方法三：滑动窗口法，方法参考滑动窗口算法

class Solution {
       public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int valid = 0;
        List<Integer> result = new ArrayList<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗⼝是否要收缩
            while (right - left >= p.length()) {
                // 终止条件
                if (valid == need.size()) {
                    result.add(left);
                }
                char d = s.charAt(left);
                left++;
                //移动left
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return result;
    }
}

方法四：由方法三改进而来，由于哈希表的长度是固定的，故上面的map可以使用数组来实现同样的效果，少量元素情况下数组空间消耗更小

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] chars = s.toCharArray();
        int len = s.length();
        int[] need = new int[26];
        int[] window = new int[26];
        for(char c:p.toCharArray()){
            need[c-'a']++;
        }
        int count=0;
        for(int num:need){
            if(num!=0){
                count++;
            }
        }
        
        int left = 0;
        int right = 0;
        int valid = 0;
        List<Integer> res = new ArrayList<>();
        while(right<len){
            char c = chars[right];
            right++;
            if(need[c-'a']!=0){
                window[c-'a']++;
                if(window[c-'a']==need[c-'a']){
                    valid++;
                }
            }

            while(right-left>=p.length()){
                if(valid==count){
                    res.add(left);
                }

                char d = chars[left];
                left++;
                if(need[d-'a']!=0){
                    if(need[d-'a']==window[d-'a']){
                        valid--;
                    }
                    window[d-'a']--;
                }
            }
        }
        return res;


    }
}

总结

持续更新中

标签：nums,int,res,height,哈希,new,left,Leetcode,刷题
From： https://blog.csdn.net/destiny3168/article/details/140203454