LeetCode算法练习top100：（1）哈希、双指针、滑动窗口

水深无声 2024-02-20 11:22 19阅读 0赞

package jz.top100;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.List;
    
    public class Top100 {
        
        //1. 两数之和
        public int[] twoSum(int[] nums, int target) {
        
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < nums.length; i++) {
        
                if(map.get(target - nums[i]) != null) {
        
                    return new int[]{
        i, map.get(target - nums[i])};
                } else {
        
                    map.put(nums[i], i);
                }
            }
            return null;
        }
    
        //49. 字母异位词分组
        public List<List<String>> groupAnagrams(String[] strs) {
        
            HashMap<String, ArrayList<String>> map = new HashMap<>();
            for (String s : strs) {
        
                char[] chars = s.toCharArray();
                Arrays.sort(chars);
                String s0 = Arrays.toString(chars);
                if (map.containsKey(s0)) {
        
                    map.get(s0).add(s);
                } else {
        
                    ArrayList<String> list = new ArrayList<>();
                    list.add(s);
                    map.put(s0, list);
                }
            }
            return new ArrayList<List<String>>(map.values());
        }
    
        //128. 最长连续序列
        public int longestConsecutive(int[] nums) {
        
            //数字连续，从任意一个数组出发，遍历最长连续数组
            if (nums.length == 0) {
        
                return 0;
            }
            int cur = 1, max = 1;
            Arrays.sort(nums);
            for (int i = 1; i < nums.length; i++) {
        
                if (nums[i] == nums[i - 1] + 1) {
         //连续
                    cur++;
                    max = Math.max(max, cur);
                } else if (nums[i] == nums[i - 1]){
         //相等则忽略
                    continue;
                } else {
         //不连续，重新开始
                    cur = 1;
                }
            }
            return max;
        }
    
        //283. 移动零
        public void moveZeroes(int[] nums) {
        
            int n = nums.length;
            //把不是0的元素放到前面，剩下的元素置0
            int index = 0;
            for (int i = 0; i < n; i++) {
        
                if (nums[i] != 0) {
        
                    nums[index] = nums[i];
                    index++;
                }
            }
            for (int i = index; i < n; i++) {
        
                nums[i] = 0;
            }
        }
    
        //11. 盛最多水的容器
        public int maxArea(int[] height) {
        
            int n = height.length;
            if (n < 2) {
        
                return 0;
            }
            int res = 0;
            int left = 0, right = n - 1;
            while (left < right) {
        
                res = Math.max(res, (right - left) * (Math.min(height[left], height[right])));
                if (height[left] < height[right]) {
        
                    left++;
                } else {
        
                    right--;
                }
            }
            return res;
        }
    
        //15. 三数之和
        public List<List<Integer>> threeSum(int[] nums) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (nums.length < 3) {
        
                return res;
            }
            Arrays.sort(nums);
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
        
                map.put(nums[i], i);
            }
            int a, b, c;
            for (int i = 0; i < nums.length - 2; i = map.get(a) + 1) {
        
                a = nums[i];
                for (int j = i + 1; j < nums.length - 1; j = map.get(b) + 1) {
        
                    b = nums[j];
                    c = -a - b;
                    if (c < b) {
        
                        break;
                    }
                    if (map.containsKey(c) && map.get(c) > j) {
        
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(a);
                        list.add(b);
                        list.add(c);
                        res.add(list);
                    }
                }
            }
            return res;
        }
    
        //3. 无重复字符的最长子串
        public int lengthOfLongestSubstring(String s) {
        
            int n = s.length();
            if (n <= 1) {
        
                return n;
            }
            HashMap<Character,Integer> map = new HashMap<>();
            int left = 0, right = 1; //窗口左,右
            map.put(s.charAt(left), left); //初始化窗口
            int max = 1; //最长字串
            while (right < n) {
        
                Character c = s.charAt(right);
                //有重复字符，滑动窗口
                if (map.containsKey(c)) {
        
                    //left = map.get(c) + 1;
                    left = Math.max(left, map.get(c) + 1); //防止abba情况，遇到的新重复字符比上一个重复字符还要小
                }
                map.put(c, right);
                max = Math.max(max, right - left + 1);
                right++;
            }
            return max;
        }
    
        //438. 找到字符串中所有字母异位词
        public List<Integer> findAnagrams(String s, String p) {
        
            List<Integer> list = new ArrayList<>();
            if (s.length() < p.length()) {
        
                return list;
            }
            //统计滑动窗口内各个字符出现的次数,次数相同，则是异位词
            int[] scnt = new int[26];
            int[] pcnt = new int[26];
            //初始窗口
            for (int i = 0; i < p.length(); i++) {
        
                scnt[s.charAt(i) - 'a']++;
                pcnt[p.charAt(i) - 'a']++;
            }
            //判断数组是否相同可用Arrays.equals
            if (Arrays.equals(scnt, pcnt)) {
        
                list.add(0);
            }
            for (int i = p.length(); i < s.length(); i++) {
        
                //移动窗口,先减去左边界，右边界加1
                scnt[s.charAt(i - p.length()) - 'a']--;
                scnt[s.charAt(i) - 'a']++;
                if (Arrays.equals(scnt, pcnt)) {
        
                    list.add(i - p.length() + 1);
                }
            }
            return list;
        }
    }