用 Hash 表，K 是值，V 是索引。遍历数组，判断是否存在 target - nums[i] 的 K，存在就返回。
1 2 3 4 5 6 7 8 9 10 11 12 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 null ; } }
用 Hash 表，K 是原字符串，V 是一个异位词的分组。遍历数组，把每个字符串排序，作为 K，然后向 V 的 List 添加字符串元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public List<List<String>> groupAnagrams (String[] strs) { Map<String, List<String>> map = new HashMap <>(); for (String str: strs) { char [] arr = str.toCharArray(); Arrays.sort(arr); String k = new String (arr); List<String> v = map.getOrDefault(k, new ArrayList <>()); v.add(str); map.put(k, v); } return new ArrayList <>(map.values()); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 func groupAnagrams (strs []string ) string { m := map [string ][]string {} for _, str := range strs { bytesSlice := []byte (str) slices.Sort(bytesSlice) key := string (bytesSlice) m[key] = append (m[key], str) } res := make ([][]string , 0 , len (m)) for _, v := range m { res = append (res, v) } return res }
先用 Set 对数组去重，然后遍历不重复元素，判断是否存在 curr + 1 的元素，有就计数器加一。遍历时候要去重复，判断 num - 1 是否已经被统计过。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int longestConsecutive (int [] nums) { Set<Integer> set = new HashSet <>(); for (int num : nums) { set.add(num); } int res = 0 ; for (int num : set) { if (!set.contains(num - 1 )) { int count = 1 ; int curr = num; while (set.contains(curr + 1 )) { curr++; count++; } res = Math.max(res, count); } } return res; } }
双指针法，每次都进行复制，一个指针一直移动，另一个指针当且仅当遍历元素不是 0 的时移动。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public void moveZeroes (int [] nums) { int j = 0 ; for (int i = 0 ; i < nums.length; i++) { nums[j] = nums[i]; if (nums[i] != 0 ) { j++; } } for (int i = j; i < nums.length; i++) { nums[i] = 0 ; } } }
左右双指针，每次计算水容量，只移动高度低的一侧的指针，因为宽度一直在减下，必须要寻找更大的高度，才能盛更多的水。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int maxArea (int [] height) { int l = 0 ; int r = height.length - 1 ; int res = 0 ; while (l < r) { res = Math.max(res, (r - l) * Math.min(height[l], height[r])); if (height[l] < height[r]) { res = Math.max(res, (r - l) * height[l]); int curr = height[l]; while (curr >= height[l] && l < r) { l++; } } else { res = Math.max(res, (r - l) * height[r]); int curr = height[r]; while (curr >= height[r] && l < r) { r--; } } } return res; } }
先排序
固定一个元素，判断是否已经不符合条件（>0），然后跳过重复元素（nums[i] == nums[i - 1]）。
双指针查询，找到符合条件的后，需要移动指针，移动过程中需要去重。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public List<List<Integer>> threeSum (int [] nums) { List<List<Integer>> res = new ArrayList <>(); Arrays.sort(nums); for (int i = 0 ; i < nums.length - 2 ; i++) { if (nums[i] > 0 ) break ; if (i > 0 && nums[i] == nums[i - 1 ]) continue ; int l = i + 1 ; int r = nums.length - 1 ; while (l < r) { int sum = nums[l] + nums[r] + nums[i]; if (sum == 0 ) { while (l < r && nums[r] == nums[r - 1 ]) { r--; } while (l < r && nums[l] == nums[l + 1 ]) { l++; } res.add(List.of(nums[l], nums[r], nums[i])); l++; r--; } else if (sum > 0 ) { r--; } else { l++; } } } return res; } }
单调栈实现，小于就入栈，等于就更新，大于开始接雨水。
接：推出栈顶当作底部，然后栈顶和遍历元素就是左右两边，然后计算容量，注意是 while 循环，还要继续接更左侧的水。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int trap (int [] height) { if (height.length < 2 ) return 0 ; int res = 0 ; Stack<Integer> stack = new Stack <Integer>(); stack.push(0 ); for (int i = 1 ; i < height.length; i++) { int top = stack.peek(); if (height[i] > height[top]) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int bottom = stack.pop(); if (!stack.isEmpty()) { int left = stack.peek(); int h = Math.min(height[left], height[i]) - height[bottom]; int w = i - left - 1 ; res += w * h; } } } stack.push(i); } return res; } }
双指针法，两次靠近，较小的一侧水平兜住，能明确了，大的一次还需要判断。注意 l <= r
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int trap (int [] height) { if (height.length <= 2 ) { return 0 ; } int maxLeft = height[0 ], maxRight = height[height.length - 1 ]; int l = 1 , r = height.length - 2 ; int res = 0 ; while (l <= r) { maxLeft = Math.max(maxLeft, height[l]); maxRight = Math.max(maxRight, height[r]); if (maxLeft < maxRight) { res += maxLeft - height[l++]; } else { res += maxRight - height[r--]; } } return res; } }
滑动窗移动，用 HashMap 记录出现过的字符，如果字符重复出现了，修改左边索引，是上次出现的位置后一位与当前左侧索引的最大值，一定要最大值，比如 abba 这种情况，如果不加最大判断，最后一个原来最后一个 b 作为左边界时，判断最后一个 a 的时候，左边界会错误回到第一个 b 的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int lengthOfLongestSubstring (String s) { Map<Character, Integer> map = new HashMap <>(); int res = 0 ; int i = 0 ; for (int j = 0 ; j < s.length(); j++) { char curr = s.charAt(j); if (map.containsKey(curr)) { i = Math.max(map.get(curr) + 1 , i); } res = Math.max(res, j - i + 1 ); map.put(curr, j); } return res; } }
1 2 3 4 5 6 7 8 9 10 11 12 func lengthOfLongestSubstring (s string ) int { m := map [rune ]int {} res, i := 0 , 0 for j := 0 ; j < len (s); j++ { if v, ok := m[rune (s[j])]; ok && v >= i { i = v + 1 } res = max(res, j-i+1 ) m[rune (s[j])] = j } return res }
先用一个数组记录字母出现次数，遍历 p 的长度，s 就增加，p 就减少，相当于先放入第一个窗口。然后判断，是否记录全部为0，为 0 就说明窗口是 p 的异位词。开始遍历 s，将当前元素滑出，然后滑入 i + pLen 索引的字符形成新的滑动窗。s 滑出是要减一，s 滑入是要加一，每次操作要记录 differ 区别，比如 s 滑出，如果记录位置从 1 变为 0，就说明 differ 减少了 1；如果从 0 变成了 -1，说明 differ 增加了。完成记录更新后，判断区分 differ 是否为 0 即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public List<Integer> findAnagrams (String s, String p) { List<Integer> res = new ArrayList <>(); if (s.length() < p.length()) return res; int [] record = new int [26 ]; int pLen = p.length(); for (int i = 0 ; i < p.length(); i++) { record[s.charAt(i) - 'a' ]++; record[p.charAt(i) - 'a' ]--; } int differ = 0 ; for (int i = 0 ; i < 26 ; i++) { if (record[i] != 0 ) differ++; } if (differ == 0 ) { res.add(0 ); } for (int i = 0 ; i < s.length() - p.length(); i++) { record[s.charAt(i) - 'a' ]--; if (record[s.charAt(i) - 'a' ] == 0 ) { differ--; } else if (record[s.charAt(i) - 'a' ] == -1 ) { differ++; } record[s.charAt(i + pLen) - 'a' ]++; if (record[s.charAt(i + pLen) - 'a' ] == 0 ) { differ--; } else if (record[s.charAt(i + pLen) - 'a' ] == 1 ) { differ++; } if (differ == 0 ) { res.add(i + 1 ); } } return res; } }
计算前缀和，并用 HashMap 记录出现的次数，然后遍历检查是否存在 prefix-nums[i] 的组合，有就添加出现的次数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int subarraySum (int [] nums, int k) { Map<Integer, Integer> map = new HashMap <>(); int prefix = 0 ; int res = 0 ; map.put(0 , 1 ); for (int i = 0 ; i < nums.length; i++) { prefix += nums[i]; res += map.getOrDefault(prefix - k, 0 ); map.put(prefix, map.getOrDefault(prefix, 0 ) + 1 ); } return res; } }
queue ：这是一个用于存储数组索引 的单调递减队列，保证队列中的元素在nums 数组中的值是递减的。
先检查队列的头元素是否已经滑出窗口 。i - k + 1 是当前窗口的左边界 ，如果队列的头 元素索引小于这个边界 ，说明这个元素已经过期 ，需要出队 。
通过从队尾 开始弹出 元素，确保队列中的元素单调递减 。如果当前元素大于 队尾所指向的元素，队尾元素出队 ，因为它不可能再成为最大值 。
将当前元素的索引加入 队列尾部 。
当窗口形成 （即 i 达到 k-1 或更大）时，队头 元素即为当前窗口 的最大值，因为队列是单调递减 的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int [] maxSlidingWindow(int [] nums, int k) { int [] queue = new int [nums.length]; int head = 0 ; int tail = -1 ; int [] res = new int [nums.length - k + 1 ]; for (int i = 0 ; i < nums.length; i++) { if (head <= tail && queue[head] < i - k + 1 ) { head++; } while (head <= tail && nums[queue[tail]] <= nums[i]) { tail--; } tail++; queue[tail] = i; if (i >= k - 1 ) { res[i - k + 1 ] = nums[queue[head]]; } } return res; } }
准备阶段
先统计 t 中每个字符的需求 (tFreq)，比如 t = "AABC" 会得到 {A=2, B=1, C=1}。
右指针扩展窗口
不断向右移动右指针，把遇到的字符加入窗口统计 (windowFreq)，直到窗口完全包含 t 中所有字符。
左指针收缩窗口
当满足条件时，尝试收缩 左边界，找到更小 的满足条件的子串。
每次移动左指针，检查是否减少 了某个必须字符的频次，如果减少则停止收缩，继续扩展右指针。
记录最小窗口
每次找到满足条件的窗口时，更新最小窗口 的起始位置和长度。
返回结果
最后返回找到的最小 覆盖子串。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public String minWindow (String s, String t) { if (s.length() < t.length()) return "" ; Map<Character, Integer> tFreq = new HashMap <>(); for (char c : t.toCharArray()) { tFreq.put(c, tFreq.getOrDefault(c, 0 ) + 1 ); } int left = 0 , count = 0 ; int minLen = Integer.MAX_VALUE; int start = 0 ; Map<Character, Integer> windowFreq = new HashMap <>(); for (int right = 0 ; right < s.length(); right++) { char c = s.charAt(right); windowFreq.put(c, windowFreq.getOrDefault(c, 0 ) + 1 ); if (tFreq.containsKey(c) && windowFreq.get(c) == tFreq.get(c)) { count++; } while (count == tFreq.size()) { if (right - left + 1 < minLen) { minLen = right - left + 1 ; start = left; } char leftChar = s.charAt(left); windowFreq.put(leftChar, windowFreq.get(leftChar) - 1 ); if (tFreq.containsKey(leftChar) && windowFreq.get(leftChar) < tFreq.get(leftChar)) { count--; } left++; } } return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen); } }
动态规划，dp 数组表示以 i 结尾的索引位置的最大字数组和。
1 2 3 4 5 6 7 8 9 10 11 class Solution { public int maxSubArray (int [] nums) { int res = nums[0 ]; int currMax = nums[0 ]; for (int i = 1 ; i < nums.length; i++) { currMax = Math.max(currMax + nums[i], nums[i]); res = Math.max(res, currMax); } return res; } }
先按照每个区间的左边界排序。
然后进行判断和更新：
当下一个区间左边界超过当前右边界 -> 记录并更新当前区间
下一个区间左边界在当前区间内 -> 不更新，只修改当前右边界。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int [][] merge(int [][] intervals) { Arrays.sort(intervals, (a, b) -> a[0 ] - b[0 ]); List<int []> res = new ArrayList <>(); int start = intervals[0 ][0 ]; int end = intervals[0 ][1 ]; for (int i = 1 ; i < intervals.length; i++) { int left = intervals[i][0 ]; int right = intervals[i][1 ]; if (left > end) { res.add(new int []{start, end}); start = left; end = right; } else { end = Math.max(end, right); } } res.add(new int []{start, end}); return res.toArray(new int [0 ][]); } }
先完全翻转，再翻转前 k 个，最后翻转剩下的。注意 K 可能超过数组长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public void rotate (int [] nums, int k) { k %= nums.length; reverse(nums, 0 , nums.length - 1 ); reverse(nums, 0 , k - 1 ); reverse(nums, k, nums.length - 1 ); } public void reverse (int [] nums, int start, int end) { while (start < end) { int tmp = nums[start]; nums[start] = nums[end]; nums[end] = tmp; start++; end--; } } }
分左右两边计算，先计算左侧的乘积：nums[i - 1] * res[i - 1]。i 是当前元素，i - 1 * i - 1 的左侧就是 i 左侧元素的乘积。
然后再计算右边，res[i]是当前 i 的左侧，然后乘 right 就是结果，之后更新 right，乘上当前元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int [] productExceptSelf(int [] nums) { int [] res = new int [nums.length]; res[0 ] = 1 ; for (int i = 1 ; i < nums.length; i++) { res[i] = nums[i - 1 ] * res[i - 1 ]; } int right = 1 ; for (int i = nums.length - 1 ; i >= 0 ; i--) { res[i] = res[i] * right; right *= nums[i]; } return res; } }
原地 Hash，先把每个元素放到自己应该的地方，nums[i] => nums[nums[i] - 1]。再遍历数组判断是不是 i + 1 即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int firstMissingPositive (int [] nums) { for (int i = 0 ; i < nums.length; i++) { while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1 ]) { int tmp = nums[nums[i] - 1 ]; nums[nums[i] - 1 ] = nums[i]; nums[i] = tmp; } } for (int i = 0 ; i < nums.length; i++) { if (nums[i] != i + 1 ) { return i + 1 ; } } return nums.length + 1 ; } }
当有一个还不是 null 时候就不断循环。链表 A 走完了就回到链表 B 头节点，B 一样的逻辑。双方路程是一样的，如果两个不相交，最后会一起为 null。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class Solution { public ListNode getIntersectionNode (ListNode headA, ListNode headB) { ListNode currA = headA; ListNode currB = headB; while (currA != null || currB != null ) { if (currA == currB) { return currA; } if (currA == null ) { currA = headB; } else { currA = currA.next; } if (currB == null ) { currB = headA; } else { currB = currB.next; } } return null ; } }
就模拟，用虚拟头节点dummy，最后 dummy 是新的头节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public ListNode reverseList (ListNode head) { ListNode dummy = null ; ListNode curr = head; while (curr != null ) { ListNode tmp = curr.next; curr.next = dummy; dummy = curr; curr = tmp; } return dummy; } }
快慢指针找到中间的，然后返回后半部分，然后一一对比。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public boolean isPalindrome (ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; } ListNode dummy = null ; ListNode cur = slow; while (cur != null ) { ListNode tmp = cur.next; cur.next = dummy; dummy = cur; cur = tmp; } boolean res = true ; while (dummy != null && head != null ) { if (dummy.val != head.val) { res = false ; } dummy = dummy.next; head = head.next; } return res; } }
快慢指针，如果有环就会相遇。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class Solution { public boolean hasCycle (ListNode head) { if (head == null || head.next == null ) { return false ; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null ) { fast = fast.next.next; slow = slow.next; if (fast == slow) { return true ; } } return false ; } }
先判断是否有环，保留快慢指针相遇点，然后用双指针，一个从相遇点出发，一个从头节点出发，相遇的位置就是环入口。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class Solution { public ListNode detectCycle (ListNode head) { ListNode fast = head; ListNode slow = head; boolean hasCycle = false ; while (fast != null && fast.next != null ) { fast = fast.next.next; slow = slow.next; if (slow == fast) { hasCycle = true ; break ; } } if (!hasCycle) { return null ; } ListNode p1 = head; ListNode p2 = fast; while (p1 != p2) { p1 = p1.next; p2 = p2.next; } return p1; } }
先合并，选小的连接，让有任意一个用完了，就退出循环。然后把剩下的直接全部连上就好。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public ListNode mergeTwoLists (ListNode list1, ListNode list2) { ListNode cur = new ListNode (); ListNode dummy = cur; while (list1 != null && list2 != null ) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } if (list1 != null ) { cur.next = list1; } if (list2 != null ) { cur.next = list2; } return dummy.next; } }
没啥方法，就是模拟，最后如果还有进位的就补加一个节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public ListNode addTwoNumbers (ListNode l1, ListNode l2) { int rest = 0 ; ListNode cur = new ListNode (); ListNode dummy = cur; while (l1 != null && l2 != null ) { int sum = l1.val + l2.val + rest; int mod = sum % 10 ; cur.next = new ListNode (mod); rest = sum / 10 ; cur = cur.next; l1 = l1.next; l2 = l2.next; } while (l1 != null ) { int sum = l1.val + rest; int mod = sum % 10 ; cur.next = new ListNode (mod); rest = sum / 10 ; cur = cur.next; l1 = l1.next; } while (l2 != null ) { int sum = l2.val + rest; int mod = sum % 10 ; cur.next = new ListNode (mod); rest = sum / 10 ; cur = cur.next; l2 = l2.next; } if (rest != 0 ) { cur.next = new ListNode (rest); } return dummy.next; } }
