关于滑动窗口和双指针
  • 板块学术版
  • 楼主昒昕
  • 当前回复32
  • 已保存回复32
  • 发布时间2022/5/11 20:15
  • 上次更新2023/10/28 01:39:59
查看原帖
关于滑动窗口和双指针
84132
昒昕楼主2022/5/11 20:15

如题。

  1. “滑动窗口”、“双指针”、“尺取法”这几个东西有区别吗?

  2. 这段代码的时间复杂度是 O(n2)\mathcal{O}(n^2) 还是 O(n)\mathcal{O}(n)

 for (int i=1,j=0;i<=n&&j<=n;i++) {
        while (cnt<m&&j+1<=n) {
            j++; t[a[j]]++;
            if (t[a[j]]==1) cnt++;
        }
        if (j==n&&cnt<m) break;
        if (j-i+1<r-l+1) l=i,r=j;
        t[a[i]]--;
        if (t[a[i]]==0) cnt--;
    }
2022/5/11 20:15
加载中...