Commitbcde39a

committed

add a solution for 3

1 parent5e27b1a commitbcde39aCopy full SHA for bcde39a

File tree

+28

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _3.java
- test/java/com/fishercoder
  - _3Test.java

+28

-0

lines changed

Lines changed: 25 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -95,4 +95,29 @@ public int lengthOfLongestSubstring(String s) {`
`95`	`95`	`returnmax;`
`96`	`96`	`}`
`97`	`97`	`}`
	`98`	`+`
	`99`	`+publicstaticclassSolution5 {`
	`100`	`+/**`
	`101`	`+ * Sliding Window, my completely original idea on 9/17/2021.`
	`102`	`+ * Basically, keep moving the left boundary towards the right and keep updating the result along the way.`
	`103`	`+ * O(n) time`
	`104`	`+ * O(n) space`
	`105`	`+ */`
	`106`	`+publicintlengthOfLongestSubstring(Strings) {`
	`107`	`+intstartIndex =0;`
	`108`	`+intlongest =0;`
	`109`	`+Map<Character,Integer>map =newHashMap<>();`
	`110`	`+for (inti =0;i <s.length();i++) {`
	`111`	`+if (map.containsKey(s.charAt(i))) {`
	`112`	`+IntegerremovedIndex =map.get(s.charAt(i));`
	`113`	`+if (removedIndex >=startIndex) {`
	`114`	`+startIndex =removedIndex +1;`
	`115`	`+ }`
	`116`	`+ }`
	`117`	`+map.put(s.charAt(i),i);`
	`118`	`+longest =Math.max(longest,i -startIndex +1);`
	`119`	`+ }`
	`120`	`+returnlongest;`
	`121`	`+ }`
	`122`	`+ }`
`98`	`123`	`}`

Lines changed: 3 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -11,13 +11,15 @@ public class _3Test {`
`11`	`11`	`privatestatic_3.Solution2solution2;`
`12`	`12`	`privatestatic_3.Solution3solution3;`
`13`	`13`	`privatestatic_3.Solution4solution4;`
	`14`	`+privatestatic_3.Solution5solution5;`
`14`	`15`
`15`	`16`	`@BeforeClass`
`16`	`17`	`publicstaticvoidsetup() {`
`17`	`18`	`solution1 =new_3.Solution1();`
`18`	`19`	`solution2 =new_3.Solution2();`
`19`	`20`	`solution3 =new_3.Solution3();`
`20`	`21`	`solution4 =new_3.Solution4();`
	`22`	`+solution5 =new_3.Solution5();`
`21`	`23`	`}`
`22`	`24`
`23`	`25`	`@Test`
`@@ -26,6 +28,7 @@ public void test1() {`
`26`	`28`	`assertEquals(3,solution2.lengthOfLongestSubstring("abcabcbb"));`
`27`	`29`	`assertEquals(3,solution3.lengthOfLongestSubstring("abcabcbb"));`
`28`	`30`	`assertEquals(3,solution4.lengthOfLongestSubstring("abcabcbb"));`
	`31`	`+assertEquals(3,solution5.lengthOfLongestSubstring("abcabcbb"));`
`29`	`32`	`}`
`30`	`33`
`31`	`34`	`}`

Comments

(0)