LeetCode hot100面试背诵版（自用）

点击题目可以跳转到LeetCode

哈希

两数之和

public int[] twoSum(int[] nums, int target) {
        int length=nums.length;
        int[] ans = new int[2];
        for (int i = 0; i <length-1 ; i++) {
            for (int j = i+1; j < length; j++) {
                if(nums[i]+nums[j]==target){
                    ans[0]=i;
                    ans[1]=j;
                }
            }
        }
        return ans;
    }

字母异位词分组

public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        List<List<String>> res = new ArrayList<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();//把字符串转为数组
            Arrays.sort(chars);//排序
            String sortedStr = new String(chars);//把数组转为字符串
            List<String> tempList = map.getOrDefault(sortedStr, new ArrayList<>());//有就加入，没有就创建新的列表
            tempList.add(str);
            map.put(sortedStr,tempList);
        }
        res.addAll(map.values());
        return res;
    }

最长连续序列

public int longestConsecutive(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        Set<Integer> set = new HashSet<>();//去重
        List<Integer> list = new ArrayList<>();
        for (int i : nums) {
            set.add(i);
        }
        list.addAll(set);
        Collections.sort(list);
        int cnt=0;
        int max=0;
        for (int i = 1; i < list.size(); i++) {
            if(list.get(i)-1==list.get(i-1)){
                cnt++;
            }else {
                cnt=0;
            }
            max=Math.max(cnt,max);
        }
        return max+1;
    }

双指针

移动零

public void moveZeroes(int[] nums) {
        int temp=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){//用一个临时值，把所有非0的元素全都移动到前面
                nums[temp]=nums[i];
                temp++;
            }
        }
        while (temp<nums.length){//后面的补上0
            nums[temp]=0;
            temp++;
        }
    }

盛最多水的容器

//左右两个指针
//每次移动最短的  因为移动最短的面积有可能增大  移动长的面积一定变小
public int maxArea(int[] height) {
        int i=0;
        int j=height.length-1;
        int res=0;
        while (i<j){
            int value=Math.min(height[i],height[j])*(j-i);
            if(height[i]<height[j]){
                res=Math.max(res,value);
                i++;
            }else {
                res=Math.max(res,value);
                j--;
            }
        }
        return res;
    }

三数之和

//三重for循环超时
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        HashSet<List<Integer>> set = new HashSet<>();//去重
        for (int i = 0; i < nums.length-2; i++) {
            for (int j = i+1; j < nums.length-1; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer> list= new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        Collections.sort(list);
                        set.add(list);
                    }
                }
            }
        }
        res.addAll(set);
        return res;
    }

接雨水

//按列来看  装的水的高度为左右两边的最低高度减去自身的高度
public int trap(int[] height) {
        int sum=0;
        for (int i = 0; i < height.length; i++) {
            if(i==0||i==height.length-1){
                continue;
            }
            int left=height[i];
            int right=height[i];
            for (int j = i-1; j >=0 ; j--) {//记录左边最高高度
                if(height[j]>left){
                    left=height[j];
                }
            }
            for (int j = i+1; j <=height.length-1 ; j++) {//记录右边最高高度
                if(height[j]>right){
                    right=height[j];
                }
            }
            sum+=Math.min(left,right)-height[i];
        }
        return sum;
    }

 滑动窗口

滑动窗口算法框架

//左闭右开
public class SlidingWindow {
    /* 滑动窗口算法框架 */
    void slidingWindow(string s, string t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c:t.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0, right = 0;
        int valid = 0;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;

            // 进行窗口内数据的一系列更新
            ...

            /*** debug 输出的位置 ***/
            System.out.printf("window: [%d, %d]\n", left, right);
            /********************/

            // 判断左侧窗口是否要收缩  有时候需要控制窗口的固定大小
            while (window needs shrink) {
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                ...
            }
        }
    }
}

无重复字符的最长子串

public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int res=0;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;

            // 进行窗口内数据的一系列更新
            window.put(c,window.getOrDefault(c,0)+1);


            // 判断左侧窗口是否要收缩  有时候需要控制窗口的固定大小
            while (window.get(c)==2) {;
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                window.put(d,window.get(d)-1);
            }
            res=Math.max(res,right-left);//注意是在这里更新
        }
        return res;
    }

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

public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for (char c:p.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0, right = 0;
        int valid = 0;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            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==p.length()){
                    list.add(left);
                }
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))) valid--;
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return list;
    }

子串 

前缀和数组：其中每个元素是原始数组中从开始到当前元素的元素之和（子数组求和问题）

和为 K 的子数组

//前缀和加哈希表
public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count=0;
        int presum=0;
        map.put(0,1);// 初始化，前缀和为0出现1次
        for(int x:nums){
            presum+=x;
            if(map.containsKey(presum-k)){
                count+=map.get(presum-k);
            }
            map.put(presum,map.getOrDefault(presum,0)+1);
        }
        return count;
    }

 滑动窗口最大值

//超时 37/51
public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res=new int[nums.length-k+1];//存放所有计算出来的值
        List<Integer> temp = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            temp.add(nums[i]);
        }
        list.add(Collections.max(temp));
        for (int i = k; i < nums.length; i++) {
            temp.removeFirst();
            temp.add(nums[i]);
            list.add(Collections.max(temp));
        }
        for (int i = 0; i < res.length; i++) {
            res[i]=list.get(i);
        }
        return res;
    }

 最小覆盖子串

public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        String res="";
        int min=Integer.MAX_VALUE;
        for (char c:t.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0, right = 0;
        int valid = 0;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            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 (valid==need.size()) {
                if(right-left<min){
                    res=s.substring(left,right);
                    min=right-left;
                }
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))) valid--;
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return res;

普通数组 

矩阵置零

public void setZeroes(int[][] matrix) {
        //记录行和列中有0的坐标
        Set<Integer> rowSet = new HashSet<>();
        Set<Integer> columnSet = new HashSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j]==0){
                    rowSet.add(i);
                    columnSet.add(j);
                }
            }
        }
        //把行中有0的行  全部置为0
        for (Integer i : rowSet) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[i][j]=0;
            }
        }
        //把所有列中有0的列 全部置为0
        for (Integer i : columnSet) {
            for (int j = 0; j < matrix.length; j++) {
                matrix[j][i]=0;
            }
        }
    }

螺旋矩阵