力扣爆刷第84天之hot100五連刷6-10
文章目錄
- 力扣爆刷第84天之hot100五連刷6-10
- 一、15. 三數之和
- 二、42. 接雨水
- 三、3. 無重復字符的最長子串
- 四、438. 找到字符串中所有字母異位詞
- 五、560. 和為 K 的子數組
一、15. 三數之和
題目鏈接:https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
思路:三數之和和兩數之和類似都是使用雙指針進行操作,只不過nums數組內包含重復元素,需要考慮去重的操作,先排序,然后外層一個for內層雙指針即可完成遍歷,完成去重有兩步。
一步: if (i > 0 && nums[i] == nums[i-1]) continue;杜絕相同的nums[i]。
二步:當nums[j]+nums[k]==nums[i]時,務必保證nums[j]和nums[k]不再重復。
while(j < k && nums[j] == nums[j+1]) j++;
while(j < k && nums[k] == nums[k-1]) k--;
j++;
k--;
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> array = new ArrayList<>();Arrays.sort(nums);int len = nums.length;for(int i = 0; i < len-2; i++) {if (nums[i] > 0) break;if (i > 0 && nums[i] == nums[i-1]) continue;int j = i+1, k = len-1;while(j < k) {int temp = nums[i] + nums[j] + nums[k];if(temp == 0) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);array.add(list);while(j < k && nums[j] == nums[j+1]) j++;while(j < k && nums[k] == nums[k-1]) k--;j++;k--;}else if(temp < 0) {j++;}else {k--;}}}return array;}
}
二、42. 接雨水
題目鏈接:https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
思路:接雨水是典型的單調棧問題,只需要構造出來凹型即可,也就是棧內,自棧底到棧頂是遞減的,當遇到大于棧頂的元素時,就彈出棧頂,此時棧頂即為凹槽,然后計算面積即可。
class Solution {public int trap(int[] height) {Deque<Integer> stack = new LinkedList<>();int sum = 0;for(int i = 0; i < height.length; i++) {while(!stack.isEmpty() && height[stack.peek()] < height[i]) {int mid = stack.pop();if(!stack.isEmpty()) {int h = Math.min(height[i], height[stack.peek()]) - height[mid];int w = i - stack.peek() - 1; sum += h * w;}}stack.push(i);}return sum;}
}
三、3. 無重復字符的最長子串
題目鏈接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked
思路:如s = “abcabcbb” 長度為3,典型的滑動窗口,使用set維護不重復的子串,每次新加入元素后,更新最大長度,如果遇到重復元素,則開始縮小窗口,直到當前元素不重復,才繼續開始擴大窗口。
class Solution {public int lengthOfLongestSubstring(String s) {int max = 0;Set<Character> set = new HashSet<>();int slow = 0;for(int i = 0; i < s.length(); i++) {while(set.contains(s.charAt(i))) {set.remove(s.charAt(slow));slow++;}set.add(s.charAt(i));max = Math.max(max, set.size());}return max;}
}
四、438. 找到字符串中所有字母異位詞
題目鏈接:https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
思路:一看是異位詞基本上就得使用set或map來處理,字符串的長度又巨長,10的4次方,常規遍歷自然超時,需要使用雙指針去掉一層循環,即使用滑動窗口,維護好字符串窗口,開始時擴大窗口,順便記錄標記值,當窗口達到p字符串長度時,進行判斷,看看標記值是否符合,然后縮減窗口,這樣一次循環結束。
滑動窗口模板:
/* 滑動窗口算法框架 */
void slidingWindow(String s) {// 用合適的數據結構記錄窗口中的數據HashMap<Character, Integer> window = new HashMap<>();int left = 0, right = 0;while (right < s.length()) {// c 是將移入窗口的字符char c = s.charAt(right);window.put(c, window.getOrDefault(c, 0) + 1);// 增大窗口right++;// 進行窗口內數據的一系列更新.../*** debug 輸出的位置 ***/// 注意在最終的解法代碼中不要 print// 因為 IO 操作很耗時,可能導致超時System.out.printf("window: [%d, %d)\n", left, right);/********************/// 判斷左側窗口是否要收縮while (left < right && window needs shrink) {// d 是將移出窗口的字符char d = s.charAt(left);window.put(d, window.get(d) - 1);// 縮小窗口left++;// 進行窗口內數據的一系列更新...}}
}
題解:
class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> list = new ArrayList<>();int sLen = s.length(), pLen = p.length();if(pLen > sLen) return list;Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();for(char c : p.toCharArray()) {need.put(c, need.getOrDefault(c, 0)+1);}int left = 0, right = 0, valid = 0;while(right < sLen) {char rc = s.charAt(right);right++;if(need.containsKey(rc)) {window.put(rc, window.getOrDefault(rc, 0)+1);if(window.get(rc).equals(need.get(rc))) {valid++;}}if(right - left == pLen) {if(valid == need.size()) {list.add(left);}char lc = s.charAt(left);left++;if(need.containsKey(lc)) {if(window.get(lc).equals(need.get(lc))) {valid--;}window.put(lc, window.get(lc)-1);}}}return list;}
}
五、560. 和為 K 的子數組
題目鏈接:https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
思路:求和為k的子數組,其實就是前綴和,和使用前綴和數組的題目有點像,但是為了少一層for,把原本要存入前綴和數組的值,都存進了hashmap,然后只需要用preSum - k 去map中尋找value即可。
class Solution {public int subarraySum(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();map.put(0, 1);int count = 0, preSum = 0;for(int i = 0; i < nums.length; i++) {preSum += nums[i];if(map.containsKey(preSum - k)) {count += map.get(preSum - k);}map.put(preSum, map.getOrDefault(preSum, 0)+1);}return count;}
}