哈希
两数之和
方法一
最容易想到的方法就是枚举
x，然后去从数组中去遍历去查找是否存在target - xclass 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[] {map.get(target - nums[i]), i}; } map.put(nums[i], i); } return new int[] {-1, -1}; } }
方法二
通过遍历数组来存入Map中元素所对应的位置，通过使用哈希表来降低在查找
target - x的时间复杂度，从O(n)降到O(1)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[] {map.get(target - nums[i]), i}; } map.put(nums[i], i); } return new int[] {-1, -1}; } }
字母异位词分组
方法一
因为作为字母异位词的两个单词的所含有的字母是一样的，那这样的话它们的排序结果也是一样的，所以我们可以使用这个排序结果作为哈希表的键
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for(String str: strs) { char[] ch = str.toCharArray(); Arrays.sort(ch); String ss = Arrays.toString(ch); if(!map.containsKey(ss)) { map.put(ss, new ArrayList()); } map.get(ss).add(str); } return new ArrayList(map.values()); } }
最长连续序列
方法一
这个题简单来说就是去查找每个数的前一个数是否存在，如果存在，说明该数不是最开始的那个数，直接跳过。如果不存在，那就直接去往后延伸，找到最大可以延伸即可。
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for(int i = 0; i < nums.length; i ++) { set.add(nums[i]); } int longestSteck = 0, current = 0; for(int i: set) { if(!set.contains(i - 1)) { int steck = 1; current = i; while(set.contains(current + 1)) { current ++; steck ++; } longestSteck = Math.max(longestSteck, steck); } } return longestSteck; } }
双指针
移动零
方法一
应题目要求，必须在不复制数组的情况下原地对数组进行操作，这样的话，我们可以初始化一个指针，这个指针是指向非零元素存放的位置，然后我们遍历数组，遇到非零元素就存放到指针指向的位置，之后指针加一，最后将指针以后的位置填充零即可，只需要遍历两次数组，时间复杂度是
O(1)class Solution { public void moveZeroes(int[] nums) { int nonZeroIndex = 0; for(int i = 0; i < nums.length; i ++) { if(nums[i] != 0) { nums[nonZeroIndex ++] = nums[i]; } } for(int i = nonZeroIndex; i < nums.length; i ++) { nums[i] = 0; } } }
方法二
直接交换，通过双指针，一个指针指向的是下一个非零元素应该放的位置，然后另一个指针去遍历数组，遇到非零元素就和前一个指针交换，这样就可以保证不会该换非零元素的相对顺序了
class Solution { public void moveZeroes(int[] nums) { int nonZeroIndex = 0; for(int i = 0; i < nums.length; i ++) { if(nums[i] != 0) { int temp = nums[nonZeroIndex]; nums[nonZeroIndex] = nums[i]; nums[i] = temp; nonZeroIndex ++; } } } }
盛最多水的容器
方法一
我们可以通过双指针来计算最大容量，初始化两个指针，一个在数组开头，一个在数组末尾，不断向中间逼近，通过移动较短柱子一边的指针以求更大的容量
class Solution { public int maxArea(int[] height) { int n = height.length; int left = 0, right = n - 1; int maxx = 0; while(left < right) { int area = Math.min(height[left], height[right]) * (right - left); maxx = Math.max(maxx, area); if(height[left] < height[right]) left ++; else right --; } return maxx; } }
三数之和
方法一
应题目要求，需要满足
i < j < k并且答案中不能有重复的三元组，比如说[-1, 0, 1]和[-1, 1, 0]属于一个三元组，先对数组进行排序，之后对i进行枚举，需要预留j和k，所以枚举的范围是[0, n-3],当遇到nums[i]和nums[i-1]相等就跳过，因为题目要求不能有重复的三元组，之后就是从剩下的里面去选择两个数，这里就和两数之和Ⅱ这个题类似了，然后我们就去计算三数之和，当total > 0，我们去调整右边的指针，total < 0去调整左边的指针，不断重复直到找到满足条件的为止，当然，nums[left]和nums[right]也会有重复的问题，也需要跳过。class Solution { public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; List<List<Integer>> result = new ArrayList(); Arrays.sort(nums); for(int i = 0; i < n - 2; i ++) { if(i > 0 && nums[i] == nums[i - 1])continue; if(nums[i] + nums[i + 1] + nums[i + 2] > 0) break; if(nums[i] + nums[n - 2] + nums[n - 1] < 0) continue; int left = i + 1, right = n - 1; while(left < right) { int total = nums[i] + nums[left] + nums[right]; if(total == 0) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); left ++; while(left < right && nums[left] == nums[left - 1])left ++; right --; while(left < right && nums[right] == nums[right + 1])right --; } else if(total < 0) { left ++; } else right --; } } return result; } }
接雨水
方法一
。
。
滑动窗口
无重复字符的最长字串
方法一
这个题我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的，这样的话就可以求得最大字串长度
class Solution { public int lengthOfLongestSubstring(String s) { Set<Character> set = new HashSet<>(); int n = s.length(); int l = 0, r = 0, max = 0; while(r < n) { if(!set.contains(s.charAt(r))) { set.add(s.charAt(r++)); max = Math.max(max, r - l); } else { set.remove(s.charAt(l++)); } } return max; } }
找到字符串中所有字母异位词
方法一
这个题和上一个题类似，但是求异位词我们并不需要对字母的顺序关注，只要关注p串中各个字母出现了几次，保存下来，然后取遍历s串，不断向滑窗内添加字母，当滑窗大小与p串大小相等时比较内容，不满足滑动窗口即可
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> result = new ArrayList(); int n = s.length(), m = p.length(); int []pc = new int[27]; int []sc = new int[27]; for(int i = 0; i < m; i++) { pc[p.charAt(i) - 'a'] ++; } int l = 0, r = 0; while(r < n) { sc[s.charAt(r++) - 'a'] ++; if(r - l == m) { if(Arrays.equals(sc, pc)) { result.add(l); } sc[s.charAt(l++) - 'a'] --; } } return result; } }
字串
和为K的子数组
方法一
最容易想到的做法就是前缀和数组，通过计算前缀和数组
s来储存从数组开始到当前索引的所有元素的和。然后，通过两层嵌套循环检查所有可能的子数组并计算其和是否等于k。class Solution { public int subarraySum(int[] nums, int k) { int []s = new int[nums.length + 1]; for(int i = 1; i < s.length; i ++) { s[i] = s[i - 1] + nums[i - 1]; } int cnt = 0; for(int i = 0; i < s.length; i ++) { for(int j = i + 1; j < s.length; j ++) { if(s[j] - s[i] == k) { cnt ++; } } } return cnt; } }
方法二
，
。
滑动窗口的最大值
最小覆盖子串
普通数组
最大子数组和
方法一
动态规划，我们只需要求每个位置的
f(i)，这里的f(i)是指以第i个数结尾的最大的连续子数组和。对于f(i)，我们可以考虑nums[i]单独为一段还是加上f(i-1)，这取决于它们的大小，这样状态转移方程就有了。f(i)=max{f(i−1)+nums[i],nums[i]}class Solution { public int maxSubArray(int[] nums) { int maxx = nums[0], res = 0; for(int i = 0; i < nums.length; i++) { res = Math.max(res + nums[i], nums[i]); maxx = Math.max(res,maxx); } return maxx; } }
合并区间
方法一
对于这个题，我们只需要按照左边界进行排序，然后以此比较，只要左区间被上一个的右区间要小，说明可以覆盖，我们只要更新保存即可，比他大的话，那就单独成一个区间，再以它的右区间向后比较。
class Solution { public int[][] merge(int[][] intervals) { List<int[]> result = new ArrayList(); Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0])); int start = intervals[0][0]; int maxEnd = intervals[0][1]; for(int i = 1; i < intervals.length; i ++) { if(intervals[i][0] > maxEnd) { result.add(new int[] {start, maxEnd}); start = intervals[i][0]; maxEnd = intervals[i][1]; } else { maxEnd = Math.max(maxEnd, intervals[i][1]); } } result.add(new int[] {start, maxEnd}); return result.toArray(new int[result.size()][]); } }
轮转数组
方法一
这个题比较简单，简单说下思路，一共翻转三次，整体翻转、前部翻转、后部翻转
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; k = k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } public void reverse(int[] nums, int i, int j) { while(i < j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i ++; j --; } } }
除自身以外数组的乘积
方法一
这个题我们只需要求对应位置前后的乘积列表，最后乘起来就可以了
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] result = new int[n]; int l[] = new int[n]; int r[] = new int[n]; l[0] = 1; for(int i = 1; i < n; i ++) { l[i] = l[i - 1] * nums[i - 1]; } r[n - 1] = 1; for(int i = n - 2; i >= 0; i --) { r[i] = r[i + 1] * nums[i + 1]; } for(int i = 0; i < n; i ++) { result[i] = l[i] * r[i]; } return result; } }
缺失的第一个正数
方法一
。
、
矩阵
矩阵置零
方法一
该题不用说
class Solution { public void setZeroes(int[][] matrix) { int n = matrix.length; int m = matrix[0].length; boolean[] a = new boolean[n]; boolean[] b = new boolean[m]; for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { if(matrix[i][j] == 0) { a[i] = true; b[j] = true; } } } for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { if(a[i] || b[j]) { matrix[i][j] = 0; } } } } }
螺旋矩阵
方法一
该题只需要按层模拟即可，可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。
class Solution { public List<Integer> spiralOrder(int[][] matrix) { int n = matrix.length, m = matrix[0].length; List<Integer> result = new ArrayList(); int top = 0, bottom = n - 1, left = 0, right = m - 1; while(top <= bottom && left <= right) { for(int i = left; i <= right; i ++) { result.add(matrix[top][i]); } top ++; for(int i = top; i <= bottom; i ++) { result.add(matrix[i][right]); } right --; if(top <= bottom && left <= right) { for(int i = right; i >= left; i --) { result.add(matrix[bottom][i]); } bottom --; for(int i = bottom; i >= top; i --) { result.add(matrix[i][left]); } left ++; } } return result; } }
旋转图像
方法一
先按照对角线交换二维数组的数，然后将每一行的数再左右交换即可
class Solution { public void rotate(int[][] matrix) { int n = matrix.length; int m = matrix[0].length; for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { if(i < j) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } } for(int i = 0; i < n; i ++) { for(int j = 0; j < m/2; j ++) { int temp = matrix[i][j]; matrix[i][j] = matrix[i][m - j - 1]; matrix[i][m - j - 1] = temp; } } } }
搜索二维矩阵 II
方法一
这个题的话，我们可以从右上角来看，因为它满足向左依次减小，向下一次增大。这样的话我们只要判断目标值和当前值的关系移动即可。
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int n = matrix.length; int m = matrix[0].length; int row = 0, col = m - 1; while(row < n && col >= 0) { if(target == matrix[row][col]) return true; else if(target < matrix[row][col]) col --; else row ++; } return false; } }
链表
相交链表
方法一
题目已保证不会有环，那只要我们指针去遍历A，B就可以，因为如果存在交点，那么它们这样遍历的话到达交点的步数是一样的
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pa = headA, pb = headB; while(pa != pb) { pa = pa != null ? pa.next : headB; pb = pb != null ? pb.next : headA; } return pa; } }
反转链表
方法一
题目要求我们去反转链表，定义两个指针，一个指向head，一个指向空
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head, pre = null; while(cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }
回文链表
方法一
题目要求我们去判断是否为回文链表，可以用快慢指针来解决，可以帮助我们找到链表的中间位置，关键点在于
fast指针循环跳出的条件if(fast == null || fast.next == null) break;这里对奇数链表和偶数链表做一个简单的举例，以
fast 2j/s slow 1j/s，奇数链表，比如1 2 2，fast指针是可以正好跳完整个链表的，此时fast.next = null，这时的slow指针指向的就是中间节点；对于偶数链表，fast指针跳到最后是会有一个的剩余，那么fast.next = null，就是slow指向链表后半部分的head/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode fast = head, slow = head; while(true) { slow = slow.next; fast = fast.next.next; if(fast == null || fast.next == null) break; } ListNode sec = reverse(slow); while(sec != null) { if(head.val != sec.val) return false; head = head.next; sec = sec.next; } return true; } public ListNode reverse(ListNode head) { ListNode cur = head, pre = null; while(cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }
环形链表
方法一
判断是否为环形链表，只需要判断slow和fast能不能相遇（套圈）即可。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head == null || head.next == null) return false; ListNode fast = head, slow = head; while(true) { fast = fast.next.next; slow = slow.next; if(fast == null || fast.next == null) return false; if(slow == fast)break; } return true; } }
环形链表 II
方法一
该题与环形链表类似，在环形链表的基础上添加了获取环形链表的入环的第一个节点这一条件
快慢指针相遇
假设我们有一个环形链表，起点为
head，环的入口节点为entry。我们使用两个指针slow和fast：slow每次移动一步fast每次移动两步
假设
slow和fast在节点meet处相遇。此时slow走了s步，fast走了2s步。数学推导
由于
fast每次比slow多走一步，因此fast走的步数是slow的两倍。设环的长度为L，entry到meet节点的距离为m，head到entry节点的距离为a。那么我们可以列出以下等式：slow走了a + m步fast走了2(a + m)步
由于
fast在环内走了k圈（假设走了k圈），我们可以得到：2(a+m)=a+m+kL2(a + m) = a + m + kL2(a+m)=a+m+kL
简化得到：
a+m=kLa + m = kLa+m=kL
这意味着
a + m是环的整数倍。相遇节点与环入口节点
为了找到环的入口节点，我们需要将其中一个指针（例如
slow）移回起点（head），同时另一个指针（fast）保持在相遇点（meet）。然后两个指针都以相同的速度前进。由于
a + m = kL，即从head到entry的距离加上从entry到meet的距离等于环的整数倍，所以：slow从head开始走a步会到达entryfast从meet开始走a步（因为a + m是环的整数倍，绕过若干圈后会回到entry）
这样，两个指针会在
entry处再次相遇。/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next == null) return null; ListNode fast = head, slow = head; while(true) { slow = slow.next; fast = fast.next.next; if(fast == null || fast.next == null) return null; if(fast == slow) break; } slow = head; while(fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }
合并两个有序链表
方法一
题解：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode current = dummy; while(l1 != null && l2 != null) { if(l1.val < l2.val ) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } if(l1 != null) current.next = l1; if(l2 != null) current.next = l2; return dummy.next; } }
两数相加
方法一
题解：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode current = dummy; int res = 0, carry = 0; while(l1 != null || l2 != null) { res = carry; if(l1 != null) { res += l1.val; l1 = l1.next; } if(l2 != null) { res += l2.val; l2 = l2.next; } current.next = new ListNode(res%10); carry = res / 10; current = current.next; } if(carry > 0) { current.next = new ListNode(carry); } return dummy.next; } }
删除链表的倒数第 N 个结点
方法一
题解：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); ListNode current = dummy; dummy.next = head; for(int i = 0; i <= n; i ++) { if(current != null) { current = current.next; } else { return null; } } ListNode pre = dummy; while(current != null) { pre = pre.next; current = current.next; } pre.next = pre.next.next; return dummy.next; } }