目錄哈希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; } }