目录哈希1. 两数之和49. 字母异位词分组128. 最长连续序列双指针283. 移动零链表2. 两数相加哈希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]提示2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案进阶你可以想出一个时间复杂度小于O(n2)的算法吗class Solution { public int[] twoSum(int[] nums, int target) { // 第1步创建一个哈希表用来存数字和它的位置 java.util.MapInteger, Integer map new java.util.HashMap(); // 第2步遍历数组一个一个看 for (int i 0; i nums.length; i) { // 第3步看看当前数字需要配哪个数 int currentNumber nums[i]; int complement target - currentNumber; // 第4步检查哈希表里有没有这个配对数 boolean isFound map.containsKey(complement); // 第5步如果找到了 if (isFound true) { // 第5.1步从哈希表里取出配对数的位置 int firstIndex map.get(complement); // 第5.2步当前位置就是第二个数的位置 int secondIndex i; // 第5.3步创建一个数组用来放两个位置 int[] result new int[2]; // 第5.4步把两个位置放进数组 result[0] firstIndex; result[1] secondIndex; // 第5.5步返回这个数组 return result; } // 第6步如果没找到把当前数字和它的位置存进哈希表 map.put(currentNumber, i); } // 第7步如果遍历完了还没找到题目说不会发生 int[] emptyResult new int[0]; return emptyResult; } }49. 字母异位词分组给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。示例 1:输入:strs [eat, tea, tan, ate, nat, bat]输出:[[bat],[nat,tan],[ate,eat,tea]]解释在 strs 中没有字符串可以通过重新排列来形成bat。字符串nat和tan是字母异位词因为它们可以重新排列以形成彼此。字符串ateeat和tea是字母异位词因为它们可以重新排列以形成彼此。示例 2:输入:strs []输出:[[]]示例 3:输入:strs [a]输出:[[a]]提示1 strs.length 1040 strs[i].length 100strs[i]仅包含小写字母class Solution { public ListListString groupAnagrams(String[] strs) { // 使用 HashMapkey 是排序后的字符串value 是异位词列表 MapString, ListString map new HashMap(); for (String str : strs) { // 将字符串转换为字符数组并排序 char[] chars str.toCharArray(); Arrays.sort(chars); String sortedStr new String(chars); // 如果排序后的字符串不在 map 中创建一个新的列表 if (!map.containsKey(sortedStr)) { map.put(sortedStr, new ArrayList()); } // 将原始字符串添加到对应的列表中 map.get(sortedStr).add(str); } // 返回所有分组 return new ArrayList(map.values()); } }128. 最长连续序列给定一个未排序的整数数组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示例 3输入nums [1,0,1,2]输出3提示0 nums.length 105-109 nums[i] 109class Solution { public int longestConsecutive(int[] nums) { // 使用 HashSet 存储所有数字方便 O(1) 查找 SetInteger numSet new HashSet(); for (int num : nums) { numSet.add(num); } int longestStreak 0; // 遍历每个数字 for (int num : numSet) { // 关键优化只有当 num-1 不存在时才以 num 为起点开始计算 // 这样可以确保每个数字只被遍历一次达到 O(n) if (!numSet.contains(num - 1)) { int currentNum num; int currentStreak 1; // 不断寻找 num1, num2, ... 直到中断 while (numSet.contains(currentNum 1)) { currentNum; currentStreak; } // 更新最长长度 longestStreak Math.max(longestStreak, currentStreak); } } return longestStreak; } }双指针283. 移动零给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。请注意必须在不复制数组的情况下原地对数组进行操作。示例 1:输入:nums [0,1,0,3,12]输出:[1,3,12,0,0]示例 2:输入:nums [0]输出:[0]提示:1 nums.length 104-231 nums[i] 231 - 1进阶你能尽量减少完成的操作次数吗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[i]; nums[i] nums[nonZeroIndex]; nums[nonZeroIndex] temp; nonZeroIndex; } } } }链表2. 两数相加给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。示例 1输入l1 [2,4,3], l2 [5,6,4]输出[7,0,8]解释342 465 807.示例 2输入l1 [0], l2 [0]输出[0]示例 3输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9]输出[8,9,9,9,0,0,0,1]提示每个链表中的节点数在范围[1, 100]内0 Node.val 9题目数据保证列表表示的数字不含前导零/** * 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(0); ListNode current dummy; int carry 0; // 进位 // 遍历两个链表直到两个链表都为空且没有进位 while (l1 ! null || l2 ! null || carry ! 0) { // 获取当前节点的值如果节点为空则取0 int val1 (l1 ! null) ? l1.val : 0; int val2 (l2 ! null) ? l2.val : 0; // 计算当前位的和包括进位 int sum val1 val2 carry; // 更新进位sum 10 时进位为1否则为0 carry sum / 10; // 创建新节点值为 sum 的个位数 current.next new ListNode(sum % 10); current current.next; // 移动到下一个节点 if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } // 返回真正的头节点虚拟头节点的下一个 return dummy.next; } }