LeetCode热题100速通

一丶哈希

1、两数之和（简单）
给定一个整数数组 $n u m s$ 和一个整数目标值 $t a r g e t$ ，请你在该数组中找出和为目标值 $t a r g e t$ 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。

示例 1：输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：输入：nums = [3,3], target = 6
输出：[0,1]

方法一（自己想到）：暴力枚举，两次循环遍历所有相加的情况

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

方法二（想不到）：哈希表，遍历数组查看哈希表中是否存在target-当前数组元素值的key，如果存在返回当前数组索引和哈希表key的value，不存在把当前的数组元素和下标记录到哈希表中

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

2、字母异位词分组（中等）
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

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

示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:输入: strs = [""]
输出: [[""]]
示例 3:输入: strs = ["a"]
输出: [["a"]]

方法一：排序（想不到）
字母异位词经过排序都是相同的，可以作为哈希表的键。然后同一个组的字母异位词组成的集合作为哈希表的值

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

方法二：计数（想不到）
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。例如eat，可以表示为a1e1t1这样的形式。不过个人感觉实现起来不如方法一方便，原理其实也差不多

class Solution {public  List<List<String>> groupAnagrams(String[] strs) {HashMap<String,List<String>> map=new HashMap<>();for (String s:strs) {int[] count=new int[26];  //只有小写字母for (int i = 0; i < s.length(); i++) {count[s.charAt(i) - 'a']++;}StringBuffer sb = new StringBuffer();for (int i = 0; i < 26; i++) {if (count[i] != 0) {sb.append((char) ('a' + i));sb.append(count[i]);}}String key = sb.toString();List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(s);map.put(key, list);}return new ArrayList<>(map.values());}
}

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

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

示例 1：输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

方法一（想不到）：哈希表
先把数组的元素存在HashSet里面。然后遍历HashSet，每当遍历到一个元素x，判断x-1是否存在hash里面，存在的话就可以直接跳过，因为我们会从x-1开始寻找最长序列。如果不存在的话，就循环去hash里找x+1,x+2，直到找到所有的。

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

二、双指针

1、移动零（简单）
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1:输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:输入: nums = [0]
输出: [0]

方法一（自己想到）：双指针，一个指针指向0，一个指针非0，交换指针后，然后继续查找下一个零元素和非零元素。

class Solution {public  void moveZeroes(int[] nums) {int p1=0,p2=0;     //p1指向0元素，p2指向非0元素while (p1<nums.length&&p2<nums.length){while (p1<nums.length){if(nums[p1]==0){break;}p1++;}p2=p1+1;while (p2<nums.length){if(nums[p2]!=0){break;}p2++;}if(p1!=nums.length&&p2!=nums.length){int temp=nums[p1];nums[p1]=nums[p2];nums[p2]=temp;}}}
}

方法二（想不到）：
快慢指针，如果数组没有0，那么快慢指针始终指向同一个位置，每个位置自己和自己交换；如果数组有0，快指针先走一步，此时慢指针对应的就是0，所以要交换。

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

三、滑动窗口

四、子串

五、普通数组

六、矩阵

七、链表

八丶二叉树

九、图论

十丶回溯

十一、二分查找

1、搜索插入位置（简单）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:输入: nums = [1,3,5,6], target = 7
输出: 4

方法（自己想到）：标准的二分查找，题目多要求了一个返回没找到值的插入位置，判断一下返回mid或者mid+1就可以

class Solution {public  int searchInsert(int[] nums, int target) {int low=0,high=nums.length-1,mid=0;while(low<=high){mid=(low+high)/2;if(nums[mid]==target)return mid;else if(nums[mid]>target)high=mid-1;else low=mid+1;}if(nums[mid]>target){return mid;}return mid+1;}
}

十二、栈

十三、堆

十四丶贪心算法

十五丶动态规划

十六丶多维动态规划

十七、技巧

1、只出现一次的数字(简单)
给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：输入：nums = [2,2,1]
输出：1
示例 2 ：输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：输入：nums = [1]
输出：1

方法一：这个就是记住这个异或运算符^的定理就好了，任何数和0异或是本身，任何数和自身异或是0

class Solution {public int singleNumber(int[] nums) {int sum=nums[0];for(int i=1;i<nums.length;i++){sum^=nums[i];}return sum;}
}

2、多数元素（简单）
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：输入：nums = [3,2,3]
输出：3
示例 2：输入：nums = [2,2,1,1,1,2,2]
输出：2

方法1（自己想到）：用哈希表，遍历数组把每个元素的数量存下来，然后遍历哈希表，找出数量大于数组一半的即可

class Solution {public int majorityElement(int[] nums) {HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<nums.length;i++){if(map.containsKey(nums[i])){map.put(nums[i],map.get(nums[i])+1);}else {map.put(nums[i],1);}}for (Map.Entry<Integer,Integer> entry: map.entrySet()) {int key=entry.getKey();int value=entry.getValue();if(value>nums.length/2){return key;}}return nums[0];}
}

方法2（想不到）：Boyer-Moore 投票算法
如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

class Solution {public int majorityElement(int[] nums) {int count=0,candidate=0;for(int i=0;i<nums.length;i++){if(count==0)candidate=nums[i];if(nums[i]==candidate)count++;else count--;}return candidate;}
}