有效的字母异位词

解法一：用数组模拟哈希表

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }

        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

解法二：排序

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] char_s = s.toCharArray();
        char[] char_t = t.toCharArray();
        Arrays.sort(char_s);
        Arrays.sort(char_t);
        return Arrays.equals(char_s, char_t);
    }
}

字母异位词分组

排序后hash法：

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {

        if (strs.length == 0) return new ArrayList<>();

        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String newstr = String.valueOf(chars);
            if (!map.containsKey(newstr))
                map.put(newstr, new ArrayList<>());
            map.get(newstr).add(str);

        }
        return new ArrayList<>(map.values());
    }
}

存在重复元素

解法一：hash表
初始化set大小可以避免扩容的开销

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>(nums.length);
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
        }
        return false;
    }
}

解法二：排序+一次遍历
针对这个题，效率比hash高

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++)
            if (nums[i] == nums[i - 1]) return true;
        return false;
    }
}

最长和谐子序列

public class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> countForNum = new HashMap<>();
        for (int num : nums)
            countForNum.put(num, countForNum.getOrDefault(num, 0) + 1);
        int maxCount = 0;
        for (int num :countForNum.keySet())
            if (countForNum.containsKey(num+1))
                maxCount = Math.max(maxCount,countForNum.get(num+1)+countForNum.get(num));
        return maxCount;
    }
}

最长连续序列

public class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> countForNum = new HashSet<>();

        for (int num : nums)
            countForNum.add(num);

        //最大长度
        int maxLength = 0;

        for (int num : nums) {
            //如果num-1存在说明不是连续数字的开头，直接舍弃
            if (!countForNum.contains(num - 1)) {
                //初始化当前值和长度计数
                int curNum = num;
                int curLength = 1;

                while (countForNum.contains(curNum+1)){
                    curNum++;
                    curLength++;
                }
                maxLength = Math.max(maxLength,curLength);
            }
        }
        return maxLength;
    }
}