当前位置：首页 > news >正文

力扣100题——子串

news 来源：原创 2024/9/21 3:19:44

和为K的子数组

题目

560. 和为 K 的子数组 - 力扣（LeetCode）

思路

以一个数为基准，从这个数往后开始遍历相加，如果sum==k则count++。只要保证基准数不重复，就不会出现重复的子数组。

代码

class Solution {public int subarraySum(int[] nums, int k) {int count = 0;for(int i=0;i<nums.length;i++){int sum = 0;for(int j=i;j>=0;j--){sum = sum + nums[j];if(sum==k){count++;}}}return count;}
}

滑动窗口最大值

题目

239. 滑动窗口最大值 - 力扣（LeetCode）

思路

用双向链表保证最大值始终是链表第一个元素，每次滑动窗口的时候都把最大值保存在maxList中，最后将maxList转成数组即可

代码

public int[] maxSlidingWindow(int[] nums, int k) {LinkedList<Integer> list = new LinkedList<>();LinkedList<Integer> maxList = new LinkedList<>();list.add(nums[0]);for(int i=1;i<k;i++){if(nums[i]<list.getFirst()){list.addLast(nums[i]);}else{list.addFirst(nums[i]);}}maxList.add(list.getFirst());for(int i=k;i<nums.length;i++){int x = nums[i-k];//  System.out.println(list.contains(x)+"   "+(i-k));list.remove((Integer) i-k);if(nums[i]<list.getFirst()){list.addLast(nums[i]);}else{list.addFirst(nums[i]);}maxList.add(list.getFirst());}int []ans = new int[maxList.size()];for(int i=0;i<maxList.size();i++){ans[i] = maxList.get(i);}return ans;}

最小覆盖子串

题目

76. 最小覆盖子串 - 力扣（LeetCode）

思路

首先可以使用类似双指针的想法去理解，r,l和从最左端开始出发，r不断右移，当当前l和r的区间包括了t中所有字符时，记录下当前的l和r。再将l右移，重复上面的步骤，遍历完整个s串。

关键就在于怎么判断前l和r的区间包括了t中所有字符，可以使用两个数组分别记录当前区间中每个字符的个数和t中每个字符的个数。当每个字符个数相同或当前区间大于t中每个字符个数时，即为覆盖。

代码

public String minWindow(String S, String t) {char[] s = S.toCharArray();int m = s.length;int ansLeft = -1;int ansRight = m;int left = 0;int[] cntS = new int[128]; int[] cntT = new int[128]; for (char c : t.toCharArray()) {cntT[c]++;}for (int right = 0; right < m; right++) { cntS[s[right]]++; while (isCovered(cntS, cntT)) { if (right - left < ansRight - ansLeft) { ansLeft = left; ansRight = right;}cntS[s[left++]]--; // 左端点字母移出子串}}return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);}private boolean isCovered(int[] cntS, int[] cntT) {for (int i = 'A'; i <= 'Z'; i++) {if (cntS[i] < cntT[i]) {return false;}}for (int i = 'a'; i <= 'z'; i++) {if (cntS[i] < cntT[i]) {return false;}}return true;}