【力扣】第3题：无重复字符的最长子串解题思路

2023-10-04 20:30:52

第3题：无重复字符串的最长子串

解法一：暴力解法

1.逐个生成子字符串
2.看它是否不含有重复的字符

字符串的情况有：
1.正常字符串，即内容随机，如 'jksdhfjksdf'
2.字符串全是相同的元素，如 'bbbbbbbbbb'
3.空字符串

遇到的问题

1.PHP内存溢出问题

//错误描述
Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 16384 bytes) in E:\WebProject\PHP_Study\3\3.php on line 51
//错误代码
//生成$s的所有子字符串
function create_son_str($s){
  $son = [];
  $s = str_split($s);
  $s_len = count($s);
  for($i = 0 ; $i < $s_len ; $i++){
    $_son = '';//临时子字符串
    for($j = $i ; $j < $s_len ; $j++){
      $_son .= $s[$j]; //line 51
      array_push($son,$_son);
    }
  }
  return $son;
}
//错误发生原因：
//字符串长度过长，导致内存溢出

PHP中的memory_limit
memory_limit 是允许单个PHP脚本使用的最大服务器内存量。

//获取memory_limit
ini_get('memory_limit');
//设置memory_limit
ini_set('memory_limit','128M');
//虚拟主机可能会出现修改memory_limit的值失败的情况，需要联系虚拟主机服务商或者更换虚拟主机

解决办法：暂无

解法二：原生字符串操作函数解题

1.strpos() 函数
2.substr() 函数
3.strlen() 函数

strlen()函数

strpos()函数

substr()函数

代码

  /**
   * @param String $s
   * @return Integer
   */
  function lengthOfLongestSubstring($s) {
	$s_len = strlen($s);//获取全英文字符串的长度，用于下面的for循环
	$temp_s = '';//初始化当前最长子字符串
	$len = 0;//最长无重复子字符串的长度，输出的结果，不一定是最后temp_s的长度
	//遍历字符串，字符串也可以像数组一样通过下标索引获取字符
	for($i = 0; $i < $s_len; $i++){
		//判断当前字符是否在temp_s中
		$inTemp_s = strpos($temp_s,$s[$i]);//返回值：字符串在另一字符串中首次出现的位置，若未找到则返回false
		$temp_s .= $s[$i];//把当前字符拼接上去
		//分类讨论
		if($inTemp_s !== false){//因为位置可能是0，所以要用全等，不然会判断失误。
			//不等于false，也就是说当前字符$s[$i]已经存在temp_s中了
			$temp_s = substr($temp_s,$inTemp_s + 1);//这一步是核心点，要好好理解
			//Eg:$temp_s = 'abcdefghi',$s[$i] = 'c',那么从c所在位置开始截断是正确的，而不是用c来取代temp_s
		}
		//每循环一次，就重新判断一次$len的值
		$len = strlen($temp_s) > $len ? strlen($temp_s) : $len;
	}
	return $len;
  }

码农公寓