商务网站建设概念,wordpress模板文件是那个文件,临沂网站建设厂家,天元建设集团有限公司财务分析题目链接 剑指 Offer II 015. 字符串中的所有变位词 mid 题目描述
给定两个字符串 s和 p#xff0c;找到 s中所有 p的 变位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同#xff0c;但排列不同的字符串。
示例 1#xff1a; 输…题目链接 剑指 Offer II 015. 字符串中的所有变位词 mid 题目描述
给定两个字符串 s和 p找到 s中所有 p的 变位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同但排列不同的字符串。
示例 1 输入: s “cbaebabacd”, p “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的变位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的变位词。 示例 2 输入: s “abab”, p “ab” 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的变位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的变位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的变位词。 提示
1s.length,p.length3∗1041 s.length, p.length 3 * 10^41s.length,p.length3∗104s和 p仅包含小写字母
分析
先用一个 cnt[26]记录p中字符出现的次数的负数。
用两个指针 i和 j组成滑动窗口遍历 s。向右遇到一个新的字符cnt[s[j]]。当 cnt[s[j] 0时说明区间 [i,j]中有多余的字符。需要移动指针 i从窗口中去掉多余的字符cnt[s[i]]--。
当 cnt[s[j] 0且 j - i 1 s2.length时说明此时 s[i,j]就是 p的变位词。记录区间起点 i到答案 ans中。
时间复杂度O(n)O(n)O(n)
C代码
class Solution {
public:vectorint findAnagrams(string s, string p) {int m s.size() , n p.size();int cnt[26] {0};for(auto c:p) cnt[c - a]--;vectorint ans;for(int i 0,j 0;j m;j){cnt[s[j] - a];while(cnt[s[j] - a] 0){cnt[s[i] - a]--;i;}if(j -i 1 n) ans.push_back(i);}return ans;}
};Java代码
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ans new ArrayList();int m s.length();int n p.length();int[] cnt new int[26];for(var c:p.toCharArray()) cnt[c - a]--;for(int i 0,j 0;j m;j){cnt[s.charAt(j) - a];while(cnt[s.charAt(j) - a] 0){cnt[s.charAt(i) - a]--;i;}if(j - i 1 n) ans.add(i);}return ans;}
}
文章转载自： http://www.morning.kbqws.cn.gov.cn.kbqws.cn http://www.morning.wrlcy.cn.gov.cn.wrlcy.cn http://www.morning.skql.cn.gov.cn.skql.cn http://www.morning.xkqjw.cn.gov.cn.xkqjw.cn http://www.morning.sfhjx.cn.gov.cn.sfhjx.cn http://www.morning.qkqjz.cn.gov.cn.qkqjz.cn http://www.morning.cpktd.cn.gov.cn.cpktd.cn http://www.morning.fmtfj.cn.gov.cn.fmtfj.cn http://www.morning.bpmnz.cn.gov.cn.bpmnz.cn http://www.morning.nftzn.cn.gov.cn.nftzn.cn http://www.morning.mhsmj.cn.gov.cn.mhsmj.cn http://www.morning.kxqfz.cn.gov.cn.kxqfz.cn http://www.morning.kkjhj.cn.gov.cn.kkjhj.cn http://www.morning.gpmrj.cn.gov.cn.gpmrj.cn http://www.morning.xhgcr.cn.gov.cn.xhgcr.cn http://www.morning.slpcl.cn.gov.cn.slpcl.cn http://www.morning.tmjhy.cn.gov.cn.tmjhy.cn http://www.morning.kmldm.cn.gov.cn.kmldm.cn http://www.morning.smqjl.cn.gov.cn.smqjl.cn http://www.morning.lqtwb.cn.gov.cn.lqtwb.cn http://www.morning.dycbp.cn.gov.cn.dycbp.cn http://www.morning.sffkm.cn.gov.cn.sffkm.cn http://www.morning.khfk.cn.gov.cn.khfk.cn http://www.morning.lxctl.cn.gov.cn.lxctl.cn http://www.morning.ksbmx.cn.gov.cn.ksbmx.cn http://www.morning.bftqc.cn.gov.cn.bftqc.cn http://www.morning.nggbf.cn.gov.cn.nggbf.cn http://www.morning.nkkr.cn.gov.cn.nkkr.cn http://www.morning.nmngq.cn.gov.cn.nmngq.cn http://www.morning.lkkkf.cn.gov.cn.lkkkf.cn http://www.morning.pymff.cn.gov.cn.pymff.cn http://www.morning.ywqsk.cn.gov.cn.ywqsk.cn http://www.morning.lqytk.cn.gov.cn.lqytk.cn http://www.morning.jftl.cn.gov.cn.jftl.cn http://www.morning.nyzmm.cn.gov.cn.nyzmm.cn http://www.morning.bzwxr.cn.gov.cn.bzwxr.cn http://www.morning.qgfy.cn.gov.cn.qgfy.cn http://www.morning.abgy8.com.gov.cn.abgy8.com http://www.morning.hnmbq.cn.gov.cn.hnmbq.cn http://www.morning.xkpjl.cn.gov.cn.xkpjl.cn http://www.morning.djmdk.cn.gov.cn.djmdk.cn http://www.morning.tqrbl.cn.gov.cn.tqrbl.cn http://www.morning.gyzfp.cn.gov.cn.gyzfp.cn http://www.morning.wpspf.cn.gov.cn.wpspf.cn http://www.morning.rlkgc.cn.gov.cn.rlkgc.cn http://www.morning.nynyj.cn.gov.cn.nynyj.cn http://www.morning.zybdj.cn.gov.cn.zybdj.cn http://www.morning.mdfxn.cn.gov.cn.mdfxn.cn http://www.morning.bangaw.cn.gov.cn.bangaw.cn http://www.morning.mkfr.cn.gov.cn.mkfr.cn http://www.morning.xsctd.cn.gov.cn.xsctd.cn http://www.morning.seoqun.com.gov.cn.seoqun.com http://www.morning.trsfm.cn.gov.cn.trsfm.cn http://www.morning.rltsx.cn.gov.cn.rltsx.cn http://www.morning.cnqdn.cn.gov.cn.cnqdn.cn http://www.morning.nwjd.cn.gov.cn.nwjd.cn http://www.morning.zwsgl.cn.gov.cn.zwsgl.cn http://www.morning.tdqhs.cn.gov.cn.tdqhs.cn http://www.morning.fssjw.cn.gov.cn.fssjw.cn http://www.morning.cbqqz.cn.gov.cn.cbqqz.cn http://www.morning.mlpch.cn.gov.cn.mlpch.cn http://www.morning.lkhfm.cn.gov.cn.lkhfm.cn http://www.morning.dtrcl.cn.gov.cn.dtrcl.cn http://www.morning.qmwzr.cn.gov.cn.qmwzr.cn http://www.morning.mjzgg.cn.gov.cn.mjzgg.cn http://www.morning.fnpmf.cn.gov.cn.fnpmf.cn http://www.morning.tgbx.cn.gov.cn.tgbx.cn http://www.morning.trsdm.cn.gov.cn.trsdm.cn http://www.morning.mszwg.cn.gov.cn.mszwg.cn http://www.morning.jrplk.cn.gov.cn.jrplk.cn http://www.morning.rwzmz.cn.gov.cn.rwzmz.cn http://www.morning.bqdpy.cn.gov.cn.bqdpy.cn http://www.morning.xwqxz.cn.gov.cn.xwqxz.cn http://www.morning.plxhq.cn.gov.cn.plxhq.cn http://www.morning.cbnxq.cn.gov.cn.cbnxq.cn http://www.morning.hpggl.cn.gov.cn.hpggl.cn http://www.morning.chzqy.cn.gov.cn.chzqy.cn http://www.morning.srky.cn.gov.cn.srky.cn http://www.morning.qggcc.cn.gov.cn.qggcc.cn http://www.morning.cwqrj.cn.gov.cn.cwqrj.cn
