目录1.包含所有三种字符的子字符串数目2. 只出现一次的数字 II1.包含所有三种字符的子字符串数目给你一个字符串 s 它只包含三种字符 a, b 和 c 。请你返回 ab 和 c 都 至少 出现过一次的子字符串数目。示例 1输入s “abcabc”输出10解释包含 ab 和 c 各至少一次的子字符串为 “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” 和 “abc” (相同字符串算多次)。示例 2输入s “aaacb”输出3解释包含 ab 和 c 各至少一次的子字符串为 “aaacb”, “aacb” 和 “acb” 。示例 3输入s “abc”输出1思路只要某子字符串包含abc三种字符则以该字符串为前缀的字符串都包含abc因此用双指针分别指向字符串的左边界和后边界分别统计a,b,c的个数只要a,b,c个数均大于0即可得到从该位置起始的字符串个数。classSolution{publicintnumberOfSubstrings(Strings){//双指针做法滑动窗口inta0,b0,c0;intans0;char[]css.toCharArray();intns.length();for(inti0,j-1;jn;){//先决定哪个指针动if(a!0b!0c!0){//三个都不为0ansn-j;if(cs[i]a){a--;}elseif(cs[i]b){b--;}elseif(cs[i]c){c--;}i;}else{j;if(jn){if(cs[j]a){a;}elseif(cs[j]b){b;}elseif(cs[j]c){c;}}}}returnans;}}时间复杂度O ( n ) O(n)O(n)左右指针都从头到尾移动且每循环一次移动一位要么左指针动要么右指针动总的移动次数不超过2 n 2n2n空间复杂度O ( n ) O(n)O(n)如果这里不把字符串转化成字符数组空间复杂度为O ( 1 ) O(1)O(1)2. 只出现一次的数字 II给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。示例 1输入nums [2,2,3,2]输出3示例 2输入nums [0,1,0,1,0,1,99]输出99思路这里借鉴当一个元素出现两次时通过异或运算能直接消除掉该元素其实是逢二进一二进制的定义同样这里是逢三进一即以某一位二进制为例若该二进制位上1出现三次时变为0那么我们可以用两个二进制位来表示(ab)00表示出现(0,3,6,9,…)次1(ab)01表示出现(1,4,7,10,…)次1(ab)10表示出现(2,5,8,11,…)次1当要找到出现1次的某个数时只要求出b即可因为只有在出现1次时b的二进制位才为1出现三次时b的二进制位为0相当于忽略了出现三次的元素。如果无法理解可以看下面的例子以[2,2,3,2]为例2(0010),3(0011);a(0000),b(0000);第一个二进制上有1个1因此(ab)(01)第二个二进制位有四个1因此(ab)(01)第三个二进制位有0个1因此(ab)(00)第四个二进制位有0个1因此(ab)(00)合并得到(ab) ((00)(00)(01)(01))将ab拆开后得到a(0000),b(0011)b与数字3一致这里如何根据a,b以及num来计算新的a,b的值可以参考如何根据真值表得到逻辑表达式的计算公式只要求出真值表直接套用公式即可。classSolution{publicintsingleNumber(int[]nums){inta0,b0;for(intnum:nums){b(b^num)~a;a(a^num)~b;}returnb;}}时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)
