点击题目可以跳转到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){//后面的补上0nums[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的行 全部置为0for (Integer i : rowSet) {for (int j = 0; j < matrix[0].length; j++) {matrix[i][j]=0;}}//把所有列中有0的列 全部置为0for (Integer i : columnSet) {for (int j = 0; j < matrix.length; j++) {matrix[j][i]=0;}}}
