牛客NC170 最长不含重复字符的子字符串【高频中等 map、滑动窗口 Java,Go,PHP】

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/48d2ff79b8564c40a50fa79f9d5fa9c7

思路

    用一个hashmap记录每个字母的index
    如果这个字母已经在map里了
    说明已经有重复了
    这样就更新看这个字母上次出现的index

    需要注意的是这种情况：“bacbca”
    这里的a上次出现的index比c上次出现的index早
    如果按a上次出现的index字符串就变成： cbca
    这就有重复的
    所以： i = max(i, preIndex(a))
    这样就能保证是不重复的字符串

    重点：以每个位置i结尾往左推推多远，下面2个之一：
    i位置当前字符上次的位置能推多远p1
    i-1位置往左推的距离 p2

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        /*
          用一个hashmap记录每个字母的index
          如果这个字母已经在map里了
          说明已经有重复了
          这样就更新看这个字母上次出现的index

          需要注意的是这种情况：“bacbca”
          这里的a上次出现的index比c上次出现的index早
          如果按a上次出现的index字符串就变成： cbca
          这就有重复的
          所以： i = max(i, preIndex(a))
          这样就能保证是不重复的字符串

          以每个位置i结尾往左推推多远，下面2个之一：
          i位置当前字符上次的位置能推多远p1
          i-1位置往左推的距离 p2
           */


        if (s == null || s.length() == 0) return 0;

        int[] map = new int[256];
        for (int i = 1; i < 256 ; i++) {
            map[i] = -1;
        }

        int ans = 1;
        int pre = 1; //上一个位置，向左推了多长
        map[s.charAt(0)] = 0;
        for (int i = 1; i < s.length() ; i++) {
            int p1 = i - map[s.charAt(i)];
            int p2 =  pre + 1;
            int cur = Math.min(p1, p2);
            ans = Math.max(ans, cur);
            pre = cur;

            map[s.charAt(i)] = i;
        }

        return ans;
    }
}

参考答案Go

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return int整型
 */
func lengthOfLongestSubstring(s string) int {
	/*
	   用一个hashmap记录每个字母的index
	   如果这个字母已经在map里了
	   说明已经有重复了
	   这样就更新看这个字母上次出现的index

	   需要注意的是这种情况：“bacbca”
	   这里的a上次出现的index比c上次出现的index早
	   如果按a上次出现的index字符串就变成： cbca
	   这就有重复的
	   所以： i = max(i, preIndex(a))
	   这样就能保证是不重复的字符串

	   以每个位置i结尾往左推推多远，下面2个之一：
	   i位置当前字符上次的位置能推多远p1
	   i-1位置往左推的距离 p2
	*/

	if len(s) == 0 {
		return 0
	}

	m := [256]int{}
	for i := 1; i < 256; i++ {
		m[i-1] = -1
	}

	res := 1
	pre := 1 //i-1位置能往左推多远
	m[s[0]] = 0
	for i := 1; i < len(s); i++ {
		p1 := i - m[s[i]]
		p2 := pre + 1
		cur := p1
		if cur > p2 {
			cur = p2
		}

		if cur > res {
			res = cur
		}

		pre = cur
		m[s[i]] = i
	}
	return res
}

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return int整型
 */
function lengthOfLongestSubstring( $s )
{	/*
    用一个hashmap记录每个字母的index
    如果这个字母已经在map里了
    说明已经有重复了
    这样就更新看这个字母上次出现的index

    需要注意的是这种情况：“bacbca”
    这里的a上次出现的index比c上次出现的index早
    如果按a上次出现的index字符串就变成： cbca
    这就有重复的
    所以： i = max(i, preIndex(a))
    这样就能保证是不重复的字符串

    以每个位置i结尾往左推推多远，下面2个之一：
    i位置当前字符上次的位置能推多远p1
    i-1位置往左推的距离 p2
 */

    if($s ==null || strlen($s) ==0)
        return 0;

    $map =array();
    for($i=0;$i<strlen($s);$i++){
        if(!isset($map[$s[$i]]))
            $map[$s[$i]] =-1;
    }

    $res = 1;
    $pre =1;// i-1位置能往左推多远
    $map[$s[0]] =0;
    for($i=1;$i<strlen($s);$i++){
        $p1 = $i-$map[$s[$i]];
        $p2 = $pre+1;
        $cur =$p1;
        if($cur > $p2)
            $cur =$p2;

        if($res < $cur){
            $res = $cur;
        }

        $pre =$cur;
        $map[$s[$i]] =$i;
    }
    return $res;

}