leetCode 第三题

r囧r小猫 2022-03-02 15:54 215阅读 0赞

# 题目详情 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpeWluZzg0MTk_size_16_color_FFFFFF_t_70]

# 思路分析 #

去重的问题首先应该想到的是set数据结构。其的思路就是去利用set来进行记录当前的集合中是否有重复的元素。

class Solution {
        public int lengthOfLongestSubstring(String s) {
            Set<Character> s1 = new HashSet<Character>();
    		int len = s.length();
            int current =0;
            int maxLength = 0;
            int position = 0;
    		while(current<len){
            	if(s1.contains(s.charAt(current))){
            		
            		while(s.charAt(position)!=s.charAt(current)&&position<current){
            			s1.remove(s.charAt(position));
            			position++;
            		}
            		position++;
            		current++;
            		continue;
            	}else{
            		s1.add(s.charAt(current));
            		
            		if((current-position+1)>maxLength){
            			maxLength = current-position+1;
            		}
            	}
    			current++;
          }
            return maxLength;
        }
        
    }

同样的思路，可以改进写法写成

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length();
            Set<Character> set = new HashSet<>();
            int ans = 0, i = 0, j = 0;
            while (i < n && j < n) {
                // try to extend the range [i, j]
                if (!set.contains(s.charAt(j))){
                    set.add(s.charAt(j++));
                    ans = Math.max(ans, j - i);
                }
                else {
                    set.remove(s.charAt(i++));
                }
            }
            return ans;
        }
    }

还有一种比较讨巧的方法，就是利用数组来记录出现的次数，下一次出现同样的元素，把其index进行覆盖就行了

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length(), ans = 0;
            int[] index = new int[128]; // current index of character
            // try to extend the range [i, j]
            for (int j = 0, i = 0; j < n; j++) {
                i = Math.max(index[s.charAt(j)], i);
                ans = Math.max(ans, j - i + 1);
                index[s.charAt(j)] = j + 1;  //这个地方进行下标的覆盖，非常高效
            }
            return ans;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpeWluZzg0MTk_size_16_color_FFFFFF_t_70]: /images/20220302/5874e14db1164047bfa4cd7bab158735.png