217存在重复元素![J(9(APQ~M@8IC7(V_NVVF3.png

思路:

数组存在重复元素，可以将数组排序，然后再遍历判断，但是这样的复杂度是 NlogNNlogN，但是，一般会选择牺牲空间保时间，所以使用哈希表来解决这道题，让时间复杂度为 NN。

流程如下：
创建一个哈希表，然后从左往右遍历数组。
检测哈希表中是否已存在当前字符，若存在，直接返回结果，若不存在，将当前字符加入哈希表，供后续判断使用即可。

代码

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

#使用set()
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nlen = len(nums)
        if not nlen:return False
        nums.sort()
        l = [nums[0]]
        for i in range(1,nlen):
            if l[-1] ^ nums[i] != 0:
                l.append(nums[i])
            else:
                return True
        return False
#排序并比较相邻元素是否相同class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nlen = len(nums)
        if nlen != len(set(nums)):
            return True
        return False

705设计哈希集合![]R35BAF~1L1484HTZ]T9T7.png

思路

java:
简单数组
题目给出了 0 <= key <= 10^6 数据范围，同时限定了 key 只能是 int。
可以直接使用一个 boolean 数组记录某个 key 是否存在，key 直接对应 boolean 的下标。

链表

python:
哈希函数中的键值一般要%于一个底数，底数一般为素数，题目指出最多调用次数为10^4, 所以底数一般为三到四位数的素数即可,巧用Python的二维数组

代码

class MyHashSet {
    boolean[] nodes = new boolean[1000009];
    public void add(int key) {
        nodes[key] = true;
    }
    public void remove(int key) {
        nodes[key] = false;
    }
    public boolean contains(int key) {
        return nodes[key];
    }
}
class MyHashSet {
    // 由于使用的是「链表」，这个值可以取得很小
    Node[] nodes = new Node[10009];
    public void add(int key) {
        // 根据 key 获取哈希桶的位置
        int idx = getIndex(key);
        // 判断链表中是否已经存在
        Node loc = nodes[idx], tmp = loc;
        if (loc != null) {
            Node prev = null;
            while (tmp != null) {
                if (tmp.key == key) { 
                    return;
                }
                prev = tmp;
                tmp = tmp.next;
            }
            tmp = prev;
        }
        Node node = new Node(key);
        // 头插法
        // node.next = loc;
        // nodes[idx] = node;
        // 尾插法 
        if (tmp != null) {
            tmp.next = node;
        } else {
            nodes[idx] = node;
        }
    }
    public void remove(int key) {
        int idx = getIndex(key);
        Node loc = nodes[idx];
        if (loc != null) {
            Node prev = null;
            while (loc != null) {
                if (loc.key == key) {
                    if (prev != null) {
                        prev.next = loc.next;
                    } else {
                        nodes[idx] = loc.next;
                    }
                    return;
                }
                prev = loc;
                loc = loc.next;
            }
        }
    }
    public boolean contains(int key) {
        int idx = getIndex(key);
        Node loc = nodes[idx];
        if (loc != null) {
            while (loc != null) {
                if (loc.key == key) {
                    return true;
                }
                loc = loc.next;
            }
        }
        return false;
    }
    static class Node {
        private int key;
        private Node next;
        private Node(int key) {
            this.key = key;
        }
    }
    int getIndex(int key) {
        // 因为 nodes 的长度只有 10009，对应的十进制的 10011100011001（总长度为 32 位，其余高位都是 0）
        // 为了让 key 对应的 hash 高位也参与运算，这里对 hashCode 进行右移异或
        // 使得 hashCode 的高位随机性和低位随机性都能体现在低 16 位中
        int hash = Integer.hashCode(key);
        hash ^= (hash >>> 16);
        return hash % nodes.length;
    }
}

class MyHashSet:
    def __init__(self):
        self.base = 799
        self.hash_set = [[] for i in range(self.base)]
    def hash_key(self, key: int):
        return key%self.base
    def add(self, key: int) -> None:
        hash_pos = self.hash_key(key)
        if key in self.hash_set[hash_pos]:
            pass
        else:
            self.hash_set[hash_pos].append(key)
    def remove(self, key: int) -> None:
        hash_pos = self.hash_key(key)
        if key not in self.hash_set[hash_pos]:
            pass
        else:
            self.hash_set[hash_pos].remove(key)
    def contains(self, key: int) -> bool:
        hash_pos = self.hash_key(key)
        if key in self.hash_set[hash_pos]:
            return True
        else:
            return False
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)