力扣热题100(方便自己复习，自用）

• 查找两数之和是不是等于target
• 也就是我们找到一个数之后，用target将其减掉，再寻找应当对应的元素是什么
• 每找到一个数，我们就将其放在集合中，因为集合中可以去重，保证我们只遍历过一次，然后再继续遍历数组，将target减去当前的数组中的值，看看已经遍历过的数组中是不是有该值，有的话就加入返回结果。
• 没有的话就将其加入。

思想：用集合存放遍历过的数值，然后根据当前定位到的数值，判断自己寻找的数值在集合中是否出现，若出现就返回结果。

class Solution {public int[] twoSum(int[] nums, int target) {int[] res = new int[2];Map<Integer,Integer> map = new HashMap<>();if(nums.length == 0 || nums == null){return res;}for(int i = 0;i < nums.length;i++){int temp = target - nums[i];if(map.containsKey(temp)){res[0] = map.get(temp);res[1] = i;}else{map.put(nums[i],i);}}return res;}
}

思想：如果可以重组后构成一个单词，那么可以把字符串先转换成字符数组，然后对字符数组中的字母进行排序。将排序过后的字符数组转换成字符串，然后再作为键出现。然后把键一样的值添加到该键对应的列表当中即可。如果没有改键，那就创建一个新的链表，并同时把键值对插入进去。

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> map = new HashMap<>();for(String str : strs){char[] array = str.toCharArray();Arrays.sort(array);String key = new String(array);List<String> list = map.getOrDefault(key,new ArrayList<>());list.add(str);map.put(key,list);}return new ArrayList<List<String>>(map.values());}
}

思想：遍历该数组，当遍历到的元素，在该集合中有前驱的时候就跳过。也就是说，遍历到的数字必须是该序列中第一个打头的才进行处理和操作。并且要记录是当前数字打头的连续序列更长还是已经记录的旧的更长。

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> sets = new HashSet<>();for(int num : nums){sets.add(num);}int maxLong = 0;for(int set : sets ){int num = set;if(!sets.contains(num - 1)){int curLong = 1;while(sets.contains(num+1)){num++;curLong++;}maxLong = Math.max(curLong,maxLong);}}return maxLong;}
}

思想：使用双指针法进行求解，左指针先不动，指向已经处理好的序列的尾部，右指针寻找不为零的时候，如果不为零，就和left指向的元素进行交换。到最后，left之前的数组就都是不为零的，且位置没有被改变。

class Solution {public void moveZeroes(int[] nums) {int left = 0, right = 0,len = nums.length;while(right < len){if(nums[right] != 0){int temp = nums[right];nums[right] = nums[left];nums[left++] = temp;}right++;}}
}

思想：用双指针法

注意：记录的结果是从当前计算的结果和上次计算值中选取一个最大的。

class Solution {public int maxArea(int[] height) {int l = 0;int r = height.length-1;int result = 0;while(l < r){int area = Math.min(height[l],height[r])*(r-l);result = Math.max(result,area);if(height[l] <= height[r]){l++;}else{r--;}}return result;}
}

思想：对首个数字去重的时候，考虑的是他在首位出现过了，后面就不用再判断了，因为结果是不含有重复的值得。不用再用它打头了。也就是相同位置的相同的数字当前不用再考虑了，因为考虑过了。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for(int i = 0;i<nums.length;i++){if(nums[i] > 0){return result;}if(i > 0 && nums[i]==nums[i-1]){continue;}int left = i+1;int right = nums.length-1;while(left < right){if((nums[i]+nums[left]+nums[right])<0){left++;}else if((nums[i]+nums[left]+nums[right])>0){right--;}else{result.add(Arrays.asList(nums[i],nums[left],nums[right]));//此次，以num[i]打头的三元组，中间和右边的数字都不能和原先的数字相同了while(left < right && nums[left] == nums[left+1]) left++;while(left < right && nums[right] == nums[right-1]) right--;left++;right--;}}}return result;}
}

class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];int result = 0;for(int i = 1;i < nums1.length+1;i++){for(int j = 1;j < nums2.length+1;j++){if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;result = Math.max(result,dp[i][j]);}}}return result;}
}

class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp = new int[text1.length()+1][text2.length()+1];char[] s1= text1.toCharArray();char[] s2 = text2.toCharArray();for(int i = 1;i < text1.length()+1;i++){char c1 = s1[i-1];for(int j = 1;j < text2.length()+1;j++){char c2 = s2[j-1];if(c1 == c2){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[text1.length()][text2.length()];}
}

复杂度为O(n):

import java.util.HashSet;
import java.util.Set;class Solution {public int lengthOfLongestSubstring(String s) {int result = 0;int n = s.length();// 初始化左右指针int l = 0, r = 0; Set<Character> set = new HashSet<>();while (r < n) {if (!set.contains(s.charAt(r))) {// 若当前字符不在集合中，添加到集合并右移右指针set.add(s.charAt(r));r++;// 更新最大长度result = Math.max(result, r - l); } else {// 若当前字符在集合中，移除左指针指向的字符并右移左指针set.remove(s.charAt(l));l++;}}return result;}
}

class Solution {public int lengthOfLongestSubstring(String s) {int result = 0;int n = s.length();int l,r = 0;for(int i = 0;i < n;i++){l = i;r = i;Set<Character> set = new HashSet<>();while(r<n && !set.contains(s.charAt(r))){set.add(s.charAt(r));r++;}result = Math.max(result,r-l);}return result;}
}

思想：

• 先记录p中的每个字母出现了几次，顺带把前s的pn位也记录了。然后看看前pn位中，他们字符出现的次数是否相等。如果相等的话就是字母异位词。
• 然后，开始遍历后续的字符，每后移一个，就把前面的减一个。然后看现在的数量是否一致。

class Solution {public List<Integer> findAnagrams(String s, String p) {int sn = s.length();int pn = p.length();int[] s26 = new int[26];int[] p26 = new int[26];char[] sc = s.toCharArray();char[] pc = p.toCharArray();if(sn < pn){return new ArrayList<Integer>();}List<Integer> res = new ArrayList<>();for(int i = 0; i < pn;i++){s26[sc[i] - 'a']++;p26[pc[i] - 'a']++;}if(Arrays.equals(s26,p26)){res.add(0);}for(int i = 0;i < sn - pn;i++){--s26[sc[i]-'a'];++s26[sc[i+pn]-'a'];if(Arrays.equals(s26,p26)){res.add(i+1);}}return res;}
}

class Solution {public int subarraySum(int[] nums, int k) {int count = 0;for(int i = 0;i<nums.length;i++){int sum = 0;for(int j = i;j>=0;j--){sum += nums[j];if(sum == k){count++;}}}return count;}
}

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();int count = 0;int pre = 0;map.put(0,1);//前缀和为0的时候for(int i = 0;i < nums.length;i++){pre += nums[i];if(map.containsKey(pre - k)){count += map.get(pre - k);}map.put(pre,map.getOrDefault(pre,0)+1);}return count;}
}

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {ArrayDeque<Integer> deque = new ArrayDeque<>();int n = nums.length;int[] res = new int[n-k+1];int id = 0;for(int i = 0;i < n;i++){//我只存储当前窗口范围内的数据，超过这个范围我一个不要while(!deque.isEmpty() && deque.peek() < i-k+1){deque.poll();}while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){deque.pollLast();}deque.offer(i);//因为已经排好序了，直接把队头的元素加进来就可以了if(i >= k-1){res[id++] = nums[deque.peek()];}}return res;}
}

class Solution {public int maxSubArray(int[] nums) {if(nums.length == 1){return nums[0];}int sum = Integer.MIN_VALUE;int count = 0;for(int i = 0;i<nums.length;i++){count += nums[i];sum = Math.max(sum,count);if(count < 0){count = 0;}}return sum;}
}

class Solution {public int[][] merge(int[][] intervals) {int n = intervals.length;List<List<Integer>> res = new ArrayList<>();Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));int left = intervals[0][0];int right = intervals[0][1];for(int i = 1;i < n;i++){if(intervals[i][0] > right){res.add(new ArrayList(Arrays.asList(left,right)));left = intervals[i][0];right = intervals[i][1];}else{right = Math.max(right,intervals[i][1]);}}res.add(new ArrayList(Arrays.asList(left,right)));int[][] temp = new int[res.size()][2];for(int i = 0;i < res.size();i++){temp[i][0] = res.get(i).get(0);temp[i][1] = res.get(i).get(1);}return temp;}
}