华为OD机考算法题：字符串划分
题目部分
| 题目 | 字符串划分 |
| 难度 | 难 |
| 题目说明 | 给定一个小写字母组成的字符串s，请找出字符串中两个不同位置的字符作为分割点，使得字符串分成的三个连续子串且子串权重相等，注意子串不包含分割点。 若能找到满足条件的两个分割点，请输出这两个分割点在字符串中的位置下标，若不能找到满足条件的分割点请返回0,0。 子串权重计算方式为：子串所有字符的ASCII码数值之和。 |
| 输入描述 | 输入为一个字符串，字符串由 a ~ z，26 个小写字符组成，5 ≤ 字符串长度 ≤ 200。 |
| 输出描述 | 输出为两个分割点在字符串中的位置下标，以逗号分隔。 |
| 补充说明 | 补充说明只考虑唯一解，不存在一个输入多种输出解的情况。 |
| ------------------------------------------------------ | |
| 示例 | |
| 示例1 | |
| 输入 | acdbbbca |
| 输出 | 2,5 |
| 说明 | 以位置 2 和 5 作为分割点，将字符串分割为 ac、bb、ca 三个子串，每一个的子串权重都为 196，输出为 2,5。 |
| 示例2 | |
| 输入 | abcabc |
| 输出 | 0,0 |
| 说明 | 找不到符合条件的分割点，输出为0,0。 |
解读与分析
题目解读：
给定一个字符串，以字符串中的 2 个字符为分隔符，把它分成 3 个子字符串（不包含 2 个分隔符），使字符串中所有字符的 ASCII 码之和相等。输出这 2 个分隔符的下标，用 “,” 隔开，如果不存在，输出 “0,0”。
此题要么存在唯一解，要么不存在解。
分析与思路：
此题字符串的长度不超过 200 个，比较简单的思路是尝试这 2 个分隔符是所有下标的情况，判断每种情况下所分隔出 3 个字符串的 ASCII 码之和是否相等。
这种方法的时间复杂度为 O()，空间复杂度为 O(
)。
以上方法可行，不过我们还有性能更好的方法。
先计算字符串中所有字符的 ASCII 码之和（设为 asciiSum），与此同时，找出可以作为分隔符的字母的最大和最小 ASCII 码值（分别设为 minAscii 和 maxAscii）。
分隔后设三个字符串的 ASCII 码之和的最大值为 maxAsciiSum，则 maxAsciiSum 值为 asciiSum - minAscii * 2；设ASCII 码之和的最小值为 minAsciiSum，则 minAsciiSum 值为 asciiSum - maxAscii * 2。
分隔后，每个字符串ASCII 码之和的取值范围为 [ minAsciiSum / 3, maxAsciiSum / 3 ]。
顺序遍历字符串，找到第一个子字符串 ASCII 码之和在取值范围内时，第一个分隔符的所有可能下标。
倒序遍历字符串，找到第三个子字符串 ASCII 码之和在取值范围内时，第二个分隔符的所有可能下标。
根据第一个分隔符和第二个分隔符的所有下标组合，判断是否三个字符串 ASCII 码之和是否相等。如果相等，则输出这两个分隔符的下标；否则，输出 “0,0”。
此方法的时间复杂度为 O(n)，空间复杂度为 O(n)。
代码实现
Java代码
import java.util.Scanner;/*** 字符串划分* @since 2023.10.10* @version 0.1* @author Frank**/
public class StringDivision {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();processStringDivision( input );}}private static void processStringDivision( String input ){int asciiSum = 0;int minAscii = 'z'; // min初始化成最大值int maxAscii = 'a'; // max初始化成最小值for( int i = 0; i < input.length(); i ++ ){char curChar = input.charAt( i );asciiSum += curChar;if( i > 0 && i < input.length() -1 ){if( curChar < minAscii ){minAscii = curChar;}if( curChar > maxAscii ){maxAscii = curChar;}}}int eachMinSum = ( asciiSum - maxAscii * 2 ) / 3;int eachMaxSum = ( asciiSum - minAscii * 2 ) / 3 + 1; // 向上取整，避免漏掉一些情况int leftIndex = 0; int leftSum = 0;for( int i = 0; i < input.length() - 2; i ++ ){int curChar = input.charAt( i );leftSum += curChar;leftIndex ++;if( leftSum >= eachMinSum ){break;}} int rightIndex = input.length() - 1;int rightSum = 0;for( int i = input.length() - 1; i > 2; i -- ){int curChar = input.charAt( i );rightSum += curChar;rightIndex --;if( rightSum >= eachMinSum ){break;}}while( leftSum <= eachMaxSum && rightSum <= eachMaxSum && leftIndex < rightIndex ){if( leftSum < rightSum ){int curChar = input.charAt( leftIndex );if( leftSum + curChar >= eachMaxSum ){break;}leftSum += curChar;leftIndex ++;}if( leftSum > rightSum ){int curChar = input.charAt( rightIndex );if( rightSum + curChar >= eachMaxSum ){break;}rightSum += curChar;rightIndex --;}if( leftIndex >= rightIndex ){break;}// 相等的情况int theOtherSum = asciiSum - leftSum - rightSum - input.charAt( leftIndex ) - input.charAt( rightIndex );if( theOtherSum == leftSum ){System.out.println( leftIndex + "," + rightIndex);return;}// 如果 theOtherSum 不相等，继续int curChar = input.charAt( leftIndex );if( leftSum + curChar >= eachMaxSum ){break;}leftSum += curChar;leftIndex ++;curChar = input.charAt( rightIndex );if( rightSum + curChar >= eachMaxSum ){break;}rightSum += curChar;rightIndex --; }System.out.println( "0,0" );}
}JavaScript代码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {processStringDivision(line);}
}();function processStringDivision( input ) {var asciiSum = 0;var minAscii = 'z'.charCodeAt(); // min初始化成最大值var maxAscii = 'a'.charCodeAt(); // max初始化成最小值for( var i = 0; i < input.length; i ++ ){var curChar = input.charCodeAt( i );asciiSum += curChar;if( i > 0 && i < input.length -1 ){if( curChar < minAscii ){minAscii = curChar;}if( curChar > maxAscii ){maxAscii = curChar;}}}var eachMinSum = ( asciiSum - maxAscii * 2 ) / 3;var eachMaxSum = ( asciiSum - minAscii * 2 ) / 3 + 1; // 向上取整，避免漏掉一些情况var leftIndex = 0; var leftSum = 0;for( var i = 0; i < input.length - 2; i ++ ){var curChar = input.charCodeAt( i );leftSum += curChar;leftIndex ++;if( leftSum >= eachMinSum ){break;}} var rightIndex = input.length - 1;var rightSum = 0;for( var i = input.length - 1; i > 2; i -- ){var curChar = input.charCodeAt( i );rightSum += curChar;rightIndex --;if( rightSum >= eachMinSum ){break;}}while( leftSum <= eachMaxSum && rightSum <= eachMaxSum && leftIndex < rightIndex ){if( leftSum < rightSum ){var curChar = input.charCodeAt( leftIndex );if( leftSum + curChar >= eachMaxSum ){break;}leftSum += curChar;leftIndex ++;}if( leftSum > rightSum ){var curChar = input.charCodeAt( rightIndex );if( rightSum + curChar >= eachMaxSum ){break;}rightSum += curChar;rightIndex --;}if( leftIndex >= rightIndex ){break;}// 相等的情况var theOtherSum = asciiSum - leftSum - rightSum - input.charCodeAt( leftIndex ) - input.charCodeAt( rightIndex );if( theOtherSum == leftSum ){console.log( leftIndex + "," + rightIndex);return;}// 如果 theOtherSum 不相等，继续var curChar = input.charCodeAt( leftIndex );if( leftSum + curChar >= eachMaxSum ){break;}leftSum += curChar;leftIndex ++;curChar = input.charCodeAt( rightIndex );if( rightSum + curChar >= eachMaxSum ){break;}rightSum += curChar;rightIndex --; }console.log( "0,0" );
}
(完)