红尘一场 發表於 2025-6-4 18:00:00

hot100之双指针

<h3 id="移动0283">移动0(283)</h3>
<p>先看代码</p>
<pre><code class="language-c">class Solution {
    public void moveZeroes(int[] nums) {
      int idx0 = 0;
      for (int idx = 0; idx &lt; nums.length; idx++){
            if(nums != 0){
                int temp = nums;
                nums = nums;
                nums = temp;
                idx0++;
            }
      }
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>由于仅当 <code>nums == 0</code> 时 idx0和idx间距会扩大   即有idx0 ~idx 间都为0</p>
<p>idx0用于记录0的起始位置, idx 向前移动发现非0 填入idx0idx0 向右移动</p>
<ul>
<li>感悟</li>
</ul>
<p>双指针通过停一动一, 将两次遍历融合在一次遍历中, 同时维护两个指针, 处理两个数据</p>
<h3 id="盛最多水的容器011">盛最多水的容器(011)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
    public int maxArea(int[] height) {
      int res = 0;
      int lef = 0;
      int rig = height.length - 1;
      while (lef &lt; rig){
            int area = (rig - lef) * Math.min(height, height);
            res = Math.max(res, area);
            if (height &lt; height){
                lef++;
            }else rig--;
      }
      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>容器盛最多水由<strong>短板</strong>决定, 显然在相同<strong>短板</strong>下容器越宽越好 所以让左右板从最边缘开始</p>
<p>增大容器容量只能通过寻找更优最短板(lef++ OR rig--), 此时的 trade off 就是容器变窄</p>
<ul>
<li>感悟</li>
</ul>
<p>双指针技巧特别适合需要同时考虑多个值的处理场景</p>
<h3 id="三数之和015">三数之和(015)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
    public List&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
      List&lt;List&lt;Integer&gt;&gt; res = new ArrayList&lt;&gt;();
      int n = nums.length;
      Arrays.sort(nums);
      for (int i = 0; i &lt; n; i++){
            if (nums &gt; 0)   break;
            if (i &gt; 0 &amp;&amp; nums == nums) continue;

            int lef = i+1;
            int rig = n-1;
            while (lef &lt; rig){
                int sum = nums + nums + nums;
                if(sum == 0){
                  res.add(Arrays.asList(nums, nums, nums));
                  while (lef &lt; rig &amp;&amp; nums == nums)lef++;
                  while (lef &lt; rig &amp;&amp; nums == nums)rig--;
                  lef++;
                  rig--;
                }
                else if(sum &lt; 0) lef++;
                else if(sum &gt; 0) rig--;
            }
      }
      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>分解问题成定一找二 寻找 nums + nums= - nums且 k &lt; i, j &lt; n-1</p>
<p>nums 要和 (nums + nums) 为异号, 且当 nums &gt; 0 时结束</p>
<blockquote>
<p>k &lt; i , j &lt; n-1 可行性分析</p>
<p>因为 nums + nums + nums   i, j, k 可相互替换</p>
<p>k 枚举了所有 nums OR nums OR nums&lt; 0的情况</p>
</blockquote>
<p>先通过 sort 对原数组排序 →(方便去重 |便于 nums &gt; 0 时结束 )</p>
<ul>
<li>感悟</li>
</ul>
<p>写完了两数之和, 第一感觉是要以nums作target , 取nums + nums作两数之和</p>
<p>但分析之后发现 还是用了二分</p>
<blockquote>
<p>时间复杂度: 双指针O(n*logn + n²/2 ), hash O(n² + k(n))</p>
<p>双指针有 n²/2 因为只枚举小于0情况, 由实际动态浮动 , 这里就先取个2</p>
<p>k(n)指<strong>哈希计算、解决哈希冲突, 及哈希扩容</strong></p>
<p>空间复杂度: 双指针O(1), hash O(n² → 利用hashset去重)   双指针在res中操作, 而hash 还要维护set<br>
另外, hash代码实现比较麻烦   orz</p>
</blockquote>
<h3 id="接雨水042">接雨水(042)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
    public int trap(int[] height) {
      int res = 0;
      int lef = 0;
      int rig = height.length-1;
      int preMax = 0;
      int sufMax = 0;
      while (lef &lt; rig){
            preMax = Math.max(preMax, height);
            sufMax = Math.max(sufMax, height);
            res += preMax &gt; sufMax ? sufMax - height : preMax - height;
      }
      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过维护全局两侧最高板, 采用了<strong>盛最多水的容器(011)</strong>的做法 寻找最优短板</p>
<p>对遍历到的块的接水量进行计算</p>
<ul>
<li>感悟</li>
</ul>
<p>暂无</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18910798
頁: [1]
查看完整版本: hot100之双指针