目錄哈希1. 兩數(shù)之和49. 字母異位詞分組128. 最長連續(xù)序列雙指針283. 移動零鏈表2. 兩數(shù)相加哈希1. 兩數(shù)之和給定一個整數(shù)數(shù)組nums和一個整數(shù)目標值target請你在該數(shù)組中找出和為目標值target的那兩個整數(shù)并返回它們的數(shù)組下標。你可以假設每種輸入只會對應一個答案并且你不能使用兩次相同的元素。你可以按任意順序返回答案。示例 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步創(chuàng)建一個哈希表用來存數(shù)字和它的位置 java.util.MapInteger, Integer map new java.util.HashMap(); // 第2步遍歷數(shù)組一個一個看 for (int i 0; i nums.length; i) { // 第3步看看當前數(shù)字需要配哪個數(shù) int currentNumber nums[i]; int complement target - currentNumber; // 第4步檢查哈希表里有沒有這個配對數(shù) boolean isFound map.containsKey(complement); // 第5步如果找到了 if (isFound true) { // 第5.1步從哈希表里取出配對數(shù)的位置 int firstIndex map.get(complement); // 第5.2步當前位置就是第二個數(shù)的位置 int secondIndex i; // 第5.3步創(chuàng)建一個數(shù)組用來放兩個位置 int[] result new int[2]; // 第5.4步把兩個位置放進數(shù)組 result[0] firstIndex; result[1] secondIndex; // 第5.5步返回這個數(shù)組 return result; } // 第6步如果沒找到把當前數(shù)字和它的位置存進哈希表 map.put(currentNumber, i); } // 第7步如果遍歷完了還沒找到題目說不會發(fā)生 int[] emptyResult new int[0]; return emptyResult; } }49. 字母異位詞分組給你一個字符串數(shù)組請你將 字母異位詞 組合在一起?？梢园慈我忭樞蚍祷亟Y果列表。示例 1:輸入:strs [eat, tea, tan, ate, nat, bat]輸出:[[bat],[nat,tan],[ate,eat,tea]]解釋在 strs 中沒有字符串可以通過重新排列來形成bat。字符串nat和tan是字母異位詞因為它們可以重新排列以形成彼此。字符串a(chǎn)teeat和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) { // 將字符串轉換為字符數(shù)組并排序 char[] chars str.toCharArray(); Arrays.sort(chars); String sortedStr new String(chars); // 如果排序后的字符串不在 map 中創(chuàng)建一個新的列表 if (!map.containsKey(sortedStr)) { map.put(sortedStr, new ArrayList()); } // 將原始字符串添加到對應的列表中 map.get(sortedStr).add(str); } // 返回所有分組 return new ArrayList(map.values()); } }128. 最長連續(xù)序列給定一個未排序的整數(shù)數(shù)組nums找出數(shù)字連續(xù)的最長序列不要求序列元素在原數(shù)組中連續(xù)的長度。請你設計并實現(xiàn)時間復雜度為O(n)的算法解決此問題。示例 1輸入nums [100,4,200,1,3,2]輸出4解釋最長數(shù)字連續(xù)序列是 [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 存儲所有數(shù)字方便 O(1) 查找 SetInteger numSet new HashSet(); for (int num : nums) { numSet.add(num); } int longestStreak 0; // 遍歷每個數(shù)字 for (int num : numSet) { // 關鍵優(yōu)化只有當 num-1 不存在時才以 num 為起點開始計算 // 這樣可以確保每個數(shù)字只被遍歷一次達到 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. 移動零給定一個數(shù)組nums編寫一個函數(shù)將所有0移動到數(shù)組的末尾同時保持非零元素的相對順序。請注意必須在不復制數(shù)組的情況下原地對數(shù)組進行操作。示例 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進階你能盡量減少完成的操作次數(shù)嗎class Solution { public void moveZeroes(int[] nums) { // 慢指針指向下一個非零元素應該放置的位置 int nonZeroIndex 0; // 遍歷數(shù)組將非零元素依次放到前面 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. 兩數(shù)相加給你兩個非空的鏈表表示兩個非負的整數(shù)。它們每位數(shù)字都是按照逆序的方式存儲的并且每個節(jié)點只能存儲一位數(shù)字。請你將兩個數(shù)相加并以相同形式返回一個表示和的鏈表。你可以假設除了數(shù)字 0 之外這兩個數(shù)都不會以 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]提示每個鏈表中的節(jié)點數(shù)在范圍[1, 100]內(nèi)0 Node.val 9題目數(shù)據(jù)保證列表表示的數(shù)字不含前導零/** * 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) { // 創(chuàng)建虛擬頭節(jié)點方便處理邊界情況 ListNode dummy new ListNode(0); ListNode current dummy; int carry 0; // 進位 // 遍歷兩個鏈表直到兩個鏈表都為空且沒有進位 while (l1 ! null || l2 ! null || carry ! 0) { // 獲取當前節(jié)點的值如果節(jié)點為空則取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; // 創(chuàng)建新節(jié)點值為 sum 的個位數(shù) current.next new ListNode(sum % 10); current current.next; // 移動到下一個節(jié)點 if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } // 返回真正的頭節(jié)點虛擬頭節(jié)點的下一個 return dummy.next; } }