LeetCode热题100速通

一丶哈希

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

示例 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;}
}

2、盛最多水的容器（中等）
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：输入：height = [1,1]
输出：1

方法一（自己想到）：暴力。把所有情况能盛的水都列举出来，最后选择一个最大的。这样做会超出时间限制

class Solution {public  int maxArea(int[] height) {int maxWater=0;for(int i=0;i<height.length;i++){for (int j=i;j<height.length;j++){if((j-i)*Math.min(height[i],height[j])>maxWater){System.out.println(i+"-"+height[i]+"-"+height[j]+"-"+j);maxWater=(j-i)*Math.min(height[i],height[j]);}}}return maxWater;}
}

方法二：双指针（想不到）
将左右指针分别指向数组两端。因为水容量=两个指针指向的数字中较小值∗指针之间的距离。所以如果我们移动高的指针，较小值肯定不会增加，而指针距离减小，水容量必定减少。所以我们只能移动低的指针，距离减少了，但有可能较小值增加。

 public  int maxArea(int[] height) {int maxWater=0,left=0,right=height.length-1;while (left<right){if((right-left)*Math.min(height[left],height[right])>maxWater){maxWater=(right-left)*Math.min(height[left],height[right]);}if(height[left]>height[right])right--;else left++;}return maxWater;}

3、三数之和（中等）
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

方法一（自己想到）：暴力法，穷举3个数字。这里的排序和Set集合都是为了题目要求的去重。这样做会超出时间限制O（N3）

class Solution {public  List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);HashSet<String> set=new HashSet<>();List<List<Integer>> list=new ArrayList<>();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){if(!set.contains(nums[i]+"-"+nums[j]+"-"+nums[k])){set.add(nums[i]+"-"+nums[j]+"-"+nums[k]);List<Integer> list1=new ArrayList<>();list1.add(nums[i]);list1.add(nums[j]);list1.add(nums[k]);list.add(list1);}}}}}return list;}
}

方法二：折半查找（自己想到）。因为数组已经被我排序了，所以第三个循环可以改成二分查找，这样做可以勉强通过测试O(N2logN)

class Solution {public  List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);HashSet<String> set=new HashSet<>();List<List<Integer>> list=new ArrayList<>();for(int i=0;i<nums.length-2;i++){for(int j=i+1;j< nums.length-1;j++){int k=Arrays.binarySearch(nums,j+1,nums.length,-(nums[i]+nums[j]));if(k>j&&nums[i]+nums[j]+nums[k]==0){if(!set.contains(nums[i]+"-"+nums[j]+"-"+nums[k])){set.add(nums[i]+"-"+nums[j]+"-"+nums[k]);List<Integer> list1=new ArrayList<>();list1.add(nums[i]);list1.add(nums[j]);list1.add(nums[k]);list.add(list1);}}}}return list;}
}

方法三：双指针（想不到）。数组排序后，第一个循环不变，第二个循环和第三个循环可以并行的。因为要a+b+c=0，那么b增加，c就要减少。

 public static List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);HashSet<String> set=new HashSet<>();List<List<Integer>> list=new ArrayList<>();for(int i=0;i<nums.length-2;i++) {int left = i + 1, right = nums.length - 1;while (left < right) {if (nums[i] + nums[left] + nums[right] == 0) {if(!set.contains(nums[i]+"-"+nums[left]+"-"+nums[right])){set.add(nums[i]+"-"+nums[left]+"-"+nums[right]);List<Integer> list1=new ArrayList<>();list1.add(nums[i]);list1.add(nums[left]);list1.add(nums[right]);list.add(list1);}left++;right--;} else if (nums[i] + nums[left] + nums[right] > 0) {right--;}else {left++;}}}return list;}

三、滑动窗口

四、子串

五、普通数组

六、矩阵

七、链表

八丶二叉树

九、图论

十丶回溯

十一、二分查找

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;}
}