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