无重复字符的最长子串

逻辑：

• 创建一个长度为128的数组 map，用于存储每个字符最后一次出现的位置。
• 使用两个指针 begin 和 end 分别表示当前子串的起始位置和结束位置。
• 遍历字符串 s，对于每个字符 ch：如果 map[ch] 不为 -1，说明字符 ch 在之前已经出现过，需要调整 begin 的位置，将其更新为 map[ch] + 1，以确保当前子串中不含重复字符。
• 更新 map[ch] 的值为当前位置 end。
• 计算当前子串的长度，并更新 maxLength。

代码：

public int lengthOfLongestSubstring(String s) {
    int[] map = new int[128];
    Arrays.fill(map, -1);
    int begin = 0;
    int maxLength = 0;
    for (int end = 0; end < s.length(); end++) {
        char ch = s.charAt(end);
        if (map[ch] != -1) { // 重复时调整 begin
            begin = Math.max(begin, map[ch] + 1);
            map[ch] = end;
        } else { // 不重复
            map[ch] = end;
        }
        maxLength = Math.max(maxLength, end - begin + 1);
    }
    return maxLength;
}

字母异位词分组

groupAnagrams 方法：

• 这个方法接收一个字符串数组 strs 作为输入，用于将具有相同字母组成的字符串进行分组。
• 创建一个 HashMap，键为 ArrayKey 对象，值为存储字符串的列表。
• 遍历输入的字符串数组 strs，对每个字符串创建一个 ArrayKey 对象作为键，然后将该字符串加入到对应的列表中。
• 如果当前 ArrayKey 在 HashMap 中不存在，则使用 computeIfAbsent 方法创建一个新的列表，并将当前字符串加入到列表中。
• 最后，将 HashMap 中的值转换为列表并返回。

代码：

static class ArrayKey {
    int[] key = new int[26];

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        ArrayKey arrayKey = (ArrayKey) o;

        return Arrays.equals(key, arrayKey.key);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(key);
    }

    public ArrayKey(String str) {
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i); // 'a'97-97=0  'b'98-97  'a'
            key[ch - 97]++;
        }
    }
}

/*
    题目中有说明：strs[i] 仅包含小写字母
    key = [2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]  26
    key = [2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]  26
    "eaat", "teaa"
 */
public List<List<String>> groupAnagrams(String[] strs) { // 5ms
    HashMap<ArrayKey, List<String>> map = new HashMap<>();
    for (String str : strs) {
        ArrayKey key = new ArrayKey(str);
        List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
        list.add(str);
    }
    return new ArrayList<>(map.values());
}

存在重复元素

public boolean containsDuplicate(int[] nums) { // 6ms
    HashMap<Integer, Object> map = new HashMap<>(nums.length * 2);
    Object value = new Object();
    for (int key : nums) {
        Object put = map.put(key, value);
        if (put != null) {
            return true;
        }
    }
    return false;
}

或

public boolean containsDuplicate(int[] nums) { // 5ms
    HashSet<Integer> set = new HashSet<>();
    for (int key : nums) {
        if (!set.add(key)) {
            return true;
        }
    }
    return false;
}

只出现一次的数字

准备一个 Set 集合，逐一放入数组元素遇到重复的，则删除最后留下来的，就是那个没有重复的数字

public int singleNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (!set.add(num)) {
            set.remove(num);
        }
    }
    return set.toArray(new Integer[0])[0];
}

还有一种更高效率的方法就是异或

从数组的第二个元素开始遍历，对每个元素执行异或运算 num = num ^ nums[i]。

• 异或运算的性质是：相同数字进行异或运算结果为 0，任何数与 0 进行异或运算结果等于该数本身。
• 因此，对数组中所有元素进行异或运算，相同的元素会互相抵消，最终剩下的就是只出现一次的元素。

代码：

public int singleNumber(int[] nums) {
    int num = nums[0];
    for (int i = 1; i < nums.length; i++) {
        num = num ^ nums[i];
    }
    return num;
}

有效的字母异位词

public boolean isAnagram(String s, String t) { // 1ms
    return Arrays.equals(getKey(s), getKey(t));
}

private static int[] getKey(String s) {
    int[] array = new int[26];
    char[] chars = s.toCharArray();
    for (char ch : chars) {
        array[ch - 97]++;
    }
    return array;
}

有序矩阵中第 K 小的元素

这里改为查找字符串的问题

public int firstUniqChar(String s) {
    int[] array = new int[26];
    char[] chars = s.toCharArray();
    for (char ch : chars) {
        array[ch - 97]++;
    }
    for (int i = 0; i < chars.length; i++) {
        char ch = chars[i];
        if(array[ch - 97] == 1) {
            return i;
        }
    }
    return -1;
}

参考

黑马数据结构