首页 › Java论坛 › hot100之子串

陈素萱 發表於 2025-6-6 05:31:00

hot100之子串

<h3 id="和为k的子数组560">和为K的子数组(560)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
    public int subarraySum(int[] nums, int k) {
      int res = 0;
      int preSum = 0;
      Map&lt;Integer, Integer&gt; cnt = new HashMap&lt;&gt;(nums.length);
      for (int num : nums){
            cnt.merge(preSum, 1, Integer::sum);
            preSum += num;
            res += cnt.getOrDefault(**preSum - k**, 0);
      }
      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>cnt用来记录相同前缀和的前缀数量</p>
<p>一次循环一边更新相同前缀和的前缀数量, 一边将吻合的数据放入res</p>
<p><code>preSum - k</code> 是前缀和的关键<br>
<img src="https://img2024.cnblogs.com/blog/3642195/202506/3642195-20250606121010299-271692497.png"></p>
<ul>
<li>感悟</li>
</ul>
<p>只有”单调”的数据集才适合用滑动窗口, 非”单调”的前缀和才好做 , 否则每次移动窗口都带来混乱</p>
<p>“单调”指的是 任意 num&gt;0且单调递增 OR 任意 num &lt; 0 且单调递减</p>
<p><img src="https://img2024.cnblogs.com/blog/3642195/202506/3642195-20250606052925040-665722851.png"></p>
<p>不符合单调</p>
<p><img src="https://img2024.cnblogs.com/blog/3642195/202506/3642195-20250606053003174-1648662724.png"></p>
<p>符合单调</p>
<h3 id="滑动窗口最大值560">滑动窗口最大值(560)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
      int n = nums.length;
      int[] res = new int;
      Deque&lt;Integer&gt; queue = new ArrayDeque&lt;&gt;();
      for (int i = 0; i &lt; n; i++){
            while (!queue.isEmpty() &amp;&amp; nums &lt;= nums){
                queue.removeLast();
            }
            queue.addLast(i);

            if (i-k &gt;= queue.getFirst()){
                queue.removeFirst();
            }
            if(i-k+1 &gt;= 0) res = nums;
      }
      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过维护单调递减队列queue</p>
<p>队列中存储数据下标</p>
<ul>
<li>感悟</li>
</ul>
<p>很多题目都是通过存储下标 因为一个下标含有<strong>两个有效数据 →</strong> &lt;于数据集的位置, 数据的值<strong>&gt;</strong></p>
<h3 id="最小覆盖字串076">最小覆盖字串(076)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
    public String minWindow(String s, String t) {
      int needCnt = 0;
      int[] need = new int;
      for (char c : t.toCharArray()){
            if (need == 0){
                needCnt++;
            }need++;
      }
      int n = s.length();
      int resLef = -1;
      int resRig = n;

      int lef = 0;
      for (int rig = 0; rig &lt; n; rig++){
            char cR = s.charAt(rig);
            need--;
            if (need == 0){
                needCnt--;
            }
            while (needCnt == 0){
                if(resRig-resLef &gt; rig-lef){
                  resLef = lef;
                  resRig = rig;
                }
                char cL = s.charAt(lef);
                if (need == 0) needCnt++;
                need++;
                lef++;
            }
      }

      return resLef &lt; 0 ? "" : s.substring(resLef, resRig+1);
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过滑动窗口遍历</p>
<p>通过数组need存储需要各种类字符数量, needCnt 存储需要的字符种类</p>
<ul>
<li>感悟</li>
</ul>
<p>施工中…</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18913413

查看完整版本: hot100之子串