LeetCode——Longest Substring Without Repeating Characters

题目:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

解题过程:

1、分析

   题目中主要是要统计子串的长度,这样的子串要满足一个条件就是子串中没有重复的元素。要实现快速的查找,比较方便的是使用Hash表的结构。

2、思路

   在查找到相同字符的时候要删除掉相同字符前面的所有字符。所以要做好子串的第一个字符的下标的保存。

程序代码:

public static int lengthOfLongestSubstring(String s) {
		//利用hash表
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		int length = map.size();
		int lenTmp = map.size();
		char c[] = s.toCharArray();// 将字符串转换为字符数组
		int start = 0;
		
		for (int i = 0; i < c.length; i++) {
			if (map.containsKey(c[i])) {
				int j = start;
				while (c[j] != c[i]){
					map.remove(c[j]);
					j++;
				}
				map.remove(c[j]);
				start = j+1;
				map.put(c[i], i);
			} else {
				map.put(c[i], i);
			}
			lenTmp = map.size();
			length = (length < lenTmp) ? lenTmp : length;
		}
		return length;
	}         

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

671. 循环单词重复加标记

The words are same rotate words if rotate the word to the right by loop, and get...

12030
来自专栏Python小屋

使用Python寻找黑洞数

黑洞数是指这样的整数:由这个数字每位上的数字组成的最大数减去每位数字组成的最小数仍然得到这个数自身。例如3位黑洞数是495,因为954-459=495,4位数...

46330
来自专栏一“技”之长

JavaScript基础之二——方法与属性 原

    和编译型语言必须由类产生对象不同,JavaScript语言中并没有严格的类的界定,并且对象的属性和方法也可以进行动态的绑定。属性是对象中封装的一些值数据...

7320
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--递归

递归是很多算法都使用的一种编程方法。听说递归是一种十分优雅的问题解决办法,可是对于初涉递归的我,还没有形成这种独特的体会。 学习使用递归的关键在于:如何将问题分...

31280
来自专栏Python

Python中的栈溢出及解决办法

1.递归函数 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ....

41940
来自专栏desperate633

LintCode 最长公共子串代码

9210
来自专栏desperate633

LeetCode 115. Distinct Subsequences题目分析代码

给出字符串S和字符串T,计算S的不同的子序列中T出现的个数。 子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串,并且对剩下的字符的相对位置没...

8120
来自专栏about云

spark开发基础之Scala详解apply方法

问题导读 1.什么情况下调用apply方法? 2.apply你认为有哪些作用? 3.方法调用属于apply什么功能? apply网上很多资料,但是总感觉总...

39060
来自专栏LanceToBigData

Java常用类(一)之Object类详解

大家都知道Object是所有类的父类,任何类都默认继承Object 理论上Object类是所有类的父类,即直接或间接的继承java.lang.Object类。由...

26880
来自专栏Hellovass 的博客

使用递归逆序一个栈

14320

扫码关注云+社区

领取腾讯云代金券