1
class Solution {
2
    public List<List<String>> groupAnagrams(String[] strs) {
3
        //键：排好序后的字符串   值：所有排好序后与键相同的字符串原串
4
        HashMap<String,List<String>> hashMap = new HashMap<>();
5

6
        for(String s:strs){//遍历字符串数组
7

8
        //将字符串取出并转换为char数组排序，排序后重新转为字符串
9
            char[] arr = s.toCharArray();
10
            Arrays.sort(arr);
11
            String SortedString = new String(arr);
12

13
        //若有则加入hashMap中的List列表中
14
        //若没有则put进hashMap供后续String使用
15
            if(hashMap.containsKey(SortedString)){
16
                hashMap.get(SortedString).add(s);
17
            }
18
            else{
19
                List<String> newList = new ArrayList<>();
20
                newList.add(s);
21
                hashMap.put(SortedString,newList);
22
            }
23
        }
24
    //hashMap.values()用于取出所有value
25
        return new ArrayList<List<String>>(hashMap.values());
26

27
    }
28
}

1
class Solution {
2
    public int longestConsecutive(int[] nums) {
3
        int MaxCount = 0;
4
        HashSet<Integer> hashSet = new HashSet<>();
5
        for(int i:nums){//放入Set中，去重
6
            hashSet.add(i);
7
        }
8

9
        for(int i:hashSet){
10
            if(!hashSet.contains(i-1)){//判断是否为序列开头的元素
11
                int count = 1;
12

13
                int temp = i;
14
                //若是则循环向后查找
15
                while(hashSet.contains(temp+1)){
16
                    count++;
17
                    temp++;
18
                }
19
                //更新最大值
20
                if(count>MaxCount)MaxCount = count;
21
            }
22
        }
23
        return MaxCount;
24
    }
25
}

1
class Solution {
2
    public int maxArea(int[] height) {
3
        //初始化指针
4
        int left = 0,right = height.length-1;
5
        int MaxValue = 0;
6

7
        while(left<right){//向中间找板子
8
            int value = (right-left)*Math.min(height[left],height[right]);
9
            MaxValue = Math.max(value,MaxValue);//更新MaxValue
10

11
            //抛弃left，right中较短的那一个板
12
            if(height[left]<height[right]){
13
                left++;
14
            }
15
            else{
16
                right--;
17
            }
18

19
        }
20

21
        return MaxValue;
22

23
    }
24
}

1
class Solution {
2
    public List<List<Integer>> threeSum(int[] nums) {
3
        List<List<Integer>> ans = new ArrayList<>();
4
        Arrays.sort(nums);
5
        int n = nums.length;
6

7
        for (int i = 0; i < n; i++) {
8
            if (i > 0 && nums[i] == nums[i - 1])//防止重复
9
                continue;
10
            int target = -nums[i];
11

12
            //l = i+1  防止重复
13
            int l = i+1, r = n - 1;
14

15
            while (l < r) {
16
                int sum = nums[l] + nums[r];
17

18
                if (sum > target) {
19
                    r--;
20
                } else if (sum < target) {
21
                    l++;
22
                } else {
23
                    List<Integer> temp = new ArrayList<>();
24
                    temp.add(nums[i]);
25
                    temp.add(nums[l]);
26
                    temp.add(nums[r]);
27
                    ans.add(temp);
28
                    //不能直接break  还有可能有其他可能
29
                    l++;
30
                    r--;
31

32
                    //防止重复
33
                    //注意此处：nums[l]==nums[l-1]  nums[r]==nums[r+1]
34
                    //由于l是要向右动的，所以要和i-1比较，不然可能会遗漏
35
                    //r同理
36
                    //[-2,0,1,1,2]
37
                    while(l<r && nums[l]==nums[l-1])l++;
38
                    while(l<r && nums[r]==nums[r+1])r--;
39
                }
40
            }
41

42

43
        }
44

45
        return ans;
46
    }
47
}

1
class Solution {
2
    public String longestPalindrome(String s) {
3
        char[] str = s.toCharArray();
4
        int n = str.length;
5
        int ansLeft = 0;
6
        int ansRight = 0;
7

8
        //奇回文串
9
        for(int i = 0;i<n;i++){
10
            int l = i;
11
            int r = i;
12

13
            while(l>=0 && r<n && str[l] == str[r]){
14
                l--;
15
                r++;
16
            }
17

18
            if(r-l-1 > ansRight - ansLeft){
19
                ansLeft = l+1;
20
                ansRight = r;
21
            }
22
        }
23

24
        //偶回文串
25
        for(int i = 0;i<n-1;i++){
26
            int l = i;
27
            int r = i+1;
28

29
            while(l>=0 && r<n && str[l] == str[r]){
30
                l--;
31
                r++;
32
            }
33

34
            if(r-l-1 > ansRight - ansLeft){
35
                ansLeft = l+1;
36
                ansRight = r;
37
            }
38
        }
39

40
        return s.substring(ansLeft,ansRight);
41
    }
42
}

1
class Solution {
2
    public int lengthOfLongestSubstring(String s) {
3
        int left = 0,right = 0;
4
        char []str = s.toCharArray();
5
        int len = str.length;
6
        int MaxLen = 0;
7
        HashSet<Character> hs = new HashSet<>();
8

9
        while(right < len){
10
            //当右指针前移过程中，发现在哈希表中已经有过这个字符时，
11
            //1.统计结果  2.左指针开始前移缩小窗口范围
12
            if(hs.contains(str[right])){
13
                MaxLen = Math.max(MaxLen,right-left);
14
                while(hs.contains(str[right])){
15
                    //左指针前移过程中，将排出窗口外的字符移出哈希表
16
                    hs.remove(str[left++]);
17
                }
18
            }
19
            //右指针前移扩大窗口
20
                hs.add(str[right++]);
21

22
        }
23
        //最后算一遍，通过字符串长度为1或空串的特例
24
        MaxLen = Math.max(MaxLen,right-left);
25

26
        return MaxLen;
27

28
    }
29
}

1
class Solution {
2
    public List<Integer> findAnagrams(String s, String p) {
3
        int[] cntP = new int[26];
4
        char[] strp = p.toCharArray();
5
        for(char c:strp){
6
            cntP[c-'a']++;//统计各单词个数
7
        }
8

9
        List<Integer> res = new ArrayList<>();
10
        int[] cntW = new int[26];
11

12
        int left = 0,right = 0;
13
        while(right<s.length()){
14
      //当窗口尺寸<查找串长度时进行窗口的扩容
15
            while(right<s.length()&& right-left<strp.length){
16
                cntW[s.charAt(right++)-'a']++;
17
            }
18
      //长度到达后，检验
19
            if(Arrays.equals(cntP,cntW)){
20
                res.add(left);
21
            }
22

23
            //缩短窗口
24
            cntW[s.charAt(left++)-'a']--;
25

26

27
        }
28

29
        return res;
30

31
    }
32
}

1
class Solution {
2
    public int maxVowels(String s, int k) {
3
        int ans = 0;
4
        char[] str = s.toCharArray();
5
        int count = 0;
6
        for(int r = 0,l = 0;r<str.length;r++){
7
            if(str[r]=='a'||str[r]=='e'||str[r]=='i'||str[r]=='o'||str[r]=='u'){
8
                count++;
9
            }
10

11
            while(r-l+1>=k){
12
                ans = Math.max(ans,count);
13
                if(str[l]=='a'||str[l]=='e'||str[l]=='i'||str[l]=='o'||str[l]=='u'){
14
                    count--;
15
                }
16
                l++;
17
            }
18

19
        }
20
        return ans;
21
    }
22
}

1
class Solution {
2
    public int characterReplacement(String s, int k) {
3
        char[] str = s.toCharArray();
4
        int[] cnt = new int[26];//统计窗口中字符个数
5
        int res = 0;
6
        for(int left=0,right=0;right<str.length;right++){
7
            //扩窗
8
            cnt[str[right]-'A']++;
9
            //检查
10
            while(!check(cnt,k)){
11
                //若检查不通过：即当前窗口无法构成连续字符
12
                //缩小窗口
13
                cnt[str[left++]-'A']--;
14
            }
15
            res = Math.max(res,right-left+1);
16

17
        }
18
        return res;
19
    }
20

21
    public boolean check(int[] cnt,int k){
22
        int max = 0;
23
        int sum = 0;
24
        for(int i = 0;i<26;i++){
25
            //找到当前窗口中最多的字符的个数
26
            max = Math.max(max,cnt[i]);
27
            //统计窗口中字符总个数
28
            sum+=cnt[i];
29
        }
30

31
        //容错肯定是给窗口中出现的最多的字符的
32
        //这里计算除去窗口出现最多次数的其他字符的个数
33
        int remain = sum-max;
34

35
        //若其他字符个数>容错个数，说明无法使当前窗口所有字符相同
36
        return remain<=k;
37
    }
38
}

1
class Solution {
2
    public int numSubarraysWithSum(int[] nums, int goal) {
3

4
        int sum1 = 0,sum2 = 0;
5
        int ans = 0;
6

7
        for(int r = 0,l1 = 0,l2=0;r<nums.length;r++){
8
            sum1+=nums[r];
9
            sum2+=nums[r];
10

11
            //限制l1<=r  防止中间全是0的情况导致越界
12
            while(l1<=r && sum1>=goal){
13
                sum1-=nums[l1++];
14
            }
15
            //加上满足>=goal的
16
            ans+=l1;
17

18
            //限制l2<=r  防止中间全是0的情况导致越界
19
            while(l2<=r && sum2>=goal+1){
20
                sum2-=nums[l2++];
21
            }
22
            //减去满足>=goal+1的
23
            ans-=l2;
24

25
        }
26
        return ans;
27
    }
28
}

1
class Solution {
2
    public String minWindow(String S, String T) {
3
        char[] s = S.toCharArray();
4
        char[] t = T.toCharArray();
5

6
        int m = s.length;
7
        int n = t.length;
8
        if (n > m) {
9
            return "";
10
        }
11

12
        int cnt[] = new int[128];
13
        int win[] = new int[128];
14

15
        for (char ch : t) {
16
            cnt[ch]++;
17
        }
18

19
        int min = Integer.MAX_VALUE;
20
        int ansLeft = 0;
21
        int ansRight = 0;
22

23
        for (int right = 0, left = 0; right < m; right++) {
24
            win[s[right]]++;
25

26
            //check函数检验是否覆盖，注意覆盖！= 一一对应
27
            while (check(cnt, win)) {
28
                win[s[left++]]--;
29
                if (right - left + 1 < min) {
30
                    min = right - left + 1;
31
                    ansLeft = left - 1;
32
                    ansRight = right + 1;
33
                }
34
            }
35

36
        }
37

38
        return S.substring(ansLeft, ansRight);
39
    }
40

41
//check函数，用于检验win（窗口中的字母统计）是否覆盖了cnt（子串的字母统计）
42
    private boolean check(int[] cnt, int[] win) {
43
        for (int c = 'a'; c <= 'z'; c++) {
44
            if (cnt[c] > win[c]) {
45
                return false;
46
            }
47
        }
48

49
        for (int c = 'A'; c <= 'Z'; c++) {
50
            if (cnt[c] > win[c]) {
51
                return false;
52
            }
53
        }
54

55
        return true;
56
    }
57
}

1
class Solution {
2
    public int subarraySum(int[] nums, int k) {
3
        int n = nums.length;
4
        int[] sum = new int[n+1];
5
        for(int i = 0;i<n;i++){
6
            //sum[1] = nums[0]  sum[2] = nums[0] + nums[1] ...
7
            sum[i+1] = sum[i] + nums[i];
8
        }
9

10
        HashMap<Integer,Integer> hm = new HashMap<>();
11

12
        int ans = 0;
13
        //sum[0]也要算上  注意此处是n+1---sum[n] = nums[0]+... +nums[n-1]
14
        for(int i = 0;i<n+1;i++){
15
            //找i左边的符合条件的 --- i左边的元素已经被统计进hashMap
16
            //sum[i] - sum[j] = k i>j
17
            //注意i>j，所以需要在遍历的过程中去记录，记录到map里的就是j，当前遍历到的元素就是i
18
            //如此一来j都存入了map，都是已知的。从map中找j即可
19
            int target = sum[i]-k;
20

21
            ans+=hm.getOrDefault(target,0);
22

23
            if(hm.containsKey(sum[i])){
24
                hm.put(sum[i],hm.get(sum[i])+1);
25
            }
26
            else{
27
                 hm.put(sum[i],1);
28
            }
29
        }
30

31
        return ans;
32
    }
33
}

1
class Solution {
2
    public int maxSubArray(int[] nums) {
3
        int n = nums.length;
4
        int sum[] = new int[n+1];
5

6
        if(n==1){
7
            return nums[0];
8
        }
9

10
        //min用于记录[0,i]中的最小值
11
        int min = 0;
12
        //ans需设置的小一点，题目中会出现负数
13
        int ans = -1000000;
14
        for(int i = 0;i<n;i++){
15
            sum[i+1] = sum[i] + nums[i];
16
            min = Math.min(min,sum[i]);
17
            ans = Math.max(ans,sum[i+1]-min);
18
        }
19

20
        return ans;
21

22
    }
23
}

1
class Solution {
2
    public int[] maxSlidingWindow(int[] nums, int k) {
3
        //双端队列:存的是下标！！！！！！！！！！！！！
4
        Deque<Integer> q = new ArrayDeque<>();
5

6
        //对于长度为n，窗口长度为k的数组，每个窗口产生一个最大值
7
        //所以其最大值个数=n-k+1
8
        int[]ans = new int[nums.length-k+1];
9
        int count = 0;
10

11
        for(int r = 0,l = 0;r<nums.length;r++){
12
            //维护双端队列左端:
13
            //最左端的下标<l时，说明最左端的元素已经不在窗口中，需移除
14
            if(!q.isEmpty() &&q.getFirst()<l){
15
                q.removeFirst();
16
            }
17

18
            //维护双端队列右端：
19
            //当窗口中有新元素进来时，将队列右端小于等于它的值删除，并插入
20
            while(!q.isEmpty() && nums[q.getLast()]<=nums[r]){
21
                q.removeLast();
22
            }
23
            q.addLast(r);
24

25
            //当窗口元素满k个时，从单调队列中取答案并维护窗口：缩窗
26
            if(r-l+1 == k){
27
                ans[count++] = nums[q.getFirst()];
28
                l++;
29
            }
30

31
        }
32
        return ans;
33

34
    }
35
}