首页 › Java论坛 › hot100之滑动窗口

门前雪瓦上霜 發表於 2025-6-5 14:09:00

hot100之滑动窗口

<h3 id="无重复字符的最长字串003">无重复字符的最长字串(003)</h3>
<p>先看代码</p>
<pre><code class="language-c">class Solution {
    public int lengthOfLongestSubstring(String s) {
      int res = 0;
      int lef = 0;
      int rig = 0;
      int[] memo = new int;

      while (rig &lt; s.length()){
            char clef = s.charAt(lef);
            char crig = s.charAt(rig);
            if (memo &gt; 0){
                memo--;
                lef++;
                continue;
            }
            memo++;
            res = Math.max(res, rig - lef + 1);
            rig++;
      }
      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>根据题目条件&lt;无重复&gt;</p>
<p>通过lef和rig 维护一个滑动窗口, memo来记录遇到字符的次数</p>
<p>rig一直向右扩张, 当出现数字重复, 移动lef 收缩窗口</p>
<ul>
<li>感悟</li>
</ul>
<p>寻找连续区间就让人很自然而然想到滑动窗口</p>
<p>每次窗口移动只用考虑(入窗口, 出窗口)的元素对窗口整体的影响</p>
<h3 id="找到字符串中所有的字母异位词438">找到字符串中所有的字母异位词(438)</h3>
<p>先看代码</p>
<pre><code class="language-c">class Solution {
    public List&lt;Integer&gt; findAnagrams(String s, String p) {
      List&lt;Integer&gt; res = new ArrayList&lt;&gt;();
      int lef = 0;
      int rig = 0;
      int[] memo = new int;
      for (char c : p.toCharArray()){
            memo++;
      }
      while(rig &lt; s.length()){
            int idx = s.charAt(rig) - 'a';
            memo--;
            while(memo &lt; 0){
                memo++;
                lef++;
            }
            if (rig - lef + 1 == p.length()) res.add(lef);
            rig++;
      }
      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>和<strong>无重复字符的最长字串</strong>基本一致, 扩张收缩窗口, 达到条件添加到res</p>
<ul>
<li>感悟</li>
</ul>
<p>暂无</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18912259

查看完整版本: hot100之滑动窗口