集合中的元素

出现 1 次的数

136. 只出现一次的数字 easy

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

java

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int n : nums) ret ^= n;
        return ret;
    }
}

260. 只出现一次的数字 III mid

剑指 Offer 56 - I. 数组中数字出现的次数

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

不妨设目标元素为 a,b 那么 a!=b, 即 a,b 至少有 1 位不同
通过这 1 位可以区分 a,b
令 n = a^b, n 至少有一位是 1; 取 last = n&(-n), 根据这个 last 区分 a,b

java

class Solution {
    public int[] singleNumber(int[] nums) {
        int dif = 0;
        for (int e : nums) {
            dif ^= e;
        }
        int last = dif & (-dif);
        int[] res = new int[2];
        // 变成找只出现一次的单个数字
        for (int e : nums) {
            if ((e & last) == 0)
                res[0] ^= e;
            else
                res[1] ^= e;
        }
        return res;
    }
}

387. 字符串中的第一个唯一字符 easy

给定一个字符串 s, 找到它的第一个不重复的字符，并返回它的索引. 如果不存在，则返回 -1.

java

class Solution {
    public int firstUniqChar(String s) {
        int[] cnt = new int[26];
        char[] arr = s.toCharArray();
        for (char c : arr) {
            cnt[c - 'a']++;
        }
        for (int i = 0; i < arr.length; i++) {
            if (cnt[arr[i] - 'a'] == 1) return i;
        }
        return -1;
    }
}

缺失的数

41. 缺失的第一个正数 hard

给你一个未排序的整数数组 nums, 请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

把不在合适位置上的元素派发到合适的位置, 要处理负数,大数和重复数

javago

java

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int idx;
            // i=0, nums[i]=1
            while (nums[i] > 0 && nums[i] <= n && nums[idx = nums[i] - 1] != nums[i]) {
                nums[i] ^= nums[idx];
                nums[idx] ^= nums[i];
                nums[i] ^= nums[idx];
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
}

    func firstMissingPositive(nums []int) int {
        n := len(nums)
        for i := 0; i < n; i++ {
            for nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
                nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
            }
        }
        for i := 0; i < n; i++ {
            if nums[i] != i+1 {
                return i + 1
            }
        }
        return n + 1
    }

268. 丢失的数字 easy

给定一个包含 [0, n] 中 n 个数的数组 nums，找出 [0, n] 这个范围内没有出现在数组中的那个数。

索引与元素异或

java

class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= i ^ nums[i];
        }
        res ^= nums.length;
        return res;
    }
}

448. 找到所有数组中消失的数字 easy

给你一个含 n 个整数的数组 nums，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

解法用原数组做 map

找没出现过的数字, 通常是用 map 标识
idx ∈ [0,n-1] num ∈ [1,n] 用原数组就能标识

java

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 把值映射到idx, 将idx位置的值置为负
        for (int o : nums) {
            int i = Math.abs(o);
            nums[i - 1] = -Math.abs(nums[i - 1]);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) res.add(i + 1);
        }
        return res;
    }
}

重复数

287. 寻找重复数 mid

时间复杂度 O(N) 空间复杂度 O(1)
典中典, 据说花费了 Don Knuth 24 小时才解出来

给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内，可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

解法双指针找环

$i \in [0, n]; e \in [1, n];$
这个题很重要的一点是范围[1, n], 也就是说不会出现上来就是一个环, num[i]不会指向 0
如果上来就是一个环那必然找不到入度为 2 的节点

java

class Solution {
    public int findDuplicate(int[] nums) {
        int p = 0, q = 0;
        do {
            p = nums[p];
            q = nums[nums[q]];
        } while (p != q);
        p = 0;
        while (p != q) {
            p = nums[p];
            q = nums[q];
        }
        return p;
    }
}

217. 存在重复元素 easy

给你一个整数数组 nums。如果任一值在数组中出现至少两次，返回 true；如果数组中每个元素互不相同，返回 false。

java

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

36. 有效的数独 mid

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

就是让你选数据结构, Set<Character>[], 还有宫格怎么求索引

java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] row = new Set[9];
        Set<Character>[] col = new Set[9];
        Set<Character>[] fan = new Set[9];
        for (int i = 0; i < 9; i++) {
            row[i] = new HashSet<>();
            col[i] = new HashSet<>();
            fan[i] = new HashSet<>();
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                char c;
                if ((c = board[i][j]) != '.') {
                    if (row[i].contains(c)) return false;
                    else row[i].add(c);

                    if (col[j].contains(c)) return false;
                    else col[j].add(c);

                    int idx = getIdx(i, j);
                    if (fan[idx].contains(c)) return false;
                    else fan[idx].add(c);
                }
            }
        }
        return true;
    }

    private int getIdx(int r, int c) {
        return r / 3 * 3 + c / 3;
    }
}

220. 存在重复元素 III hard

LCR 057. 存在重复元素 III mid

给你一个整数数组 nums 和两个整数 k 和 t。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t，同时又满足 abs(i - j) <= k。

如果存在则返回 true，不存在返回 false。

滑动窗口内的最小差, 跟 "滑动窗口内的最大值" 不一样哦

解法 1 TreeSet

滑窗中根据 key 找到离它最近的值
窗口里不需要分别取上下界
在线查找, 窗口中不会有重复元素

java

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            // 不需要分别取上下界
            Integer ceiling = set.ceiling(nums[i] - valueDiff);
            if (ceiling != null && ceiling <= nums[i] + valueDiff) return true;
            // 维护窗口
            set.add(nums[i]);
            if (i - indexDiff >= 0) set.remove(nums[i - indexDiff]);
        }
        return false;
    }
}

解法 2 按值分桶 + 滑窗

将值取模，粗化处理
将 val 对 valDiff 取模分桶，桶里保留最后放入的 val
为什么 work: 无论几个桶，都只保存窗口中的元素；而且在线查找桶中的元素永远不会重复

java

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int id = getId(nums[i], valueDiff);
            Integer val;
            if (map.containsKey(id) ||
                (val = map.get(id + 1)) != null && Math.abs(nums[i] - val) <= valueDiff ||
                (val = map.get(id - 1)) != null && Math.abs(nums[i] - val) <= valueDiff)
                return true;
            map.put(id, nums[i]);
            if (i >= indexDiff) {
                int oldId = getId(nums[i - indexDiff], valueDiff);
                map.remove(oldId);
            }
        }
        return false;
    }

    int getId(int x, int width) {
        if (width == 0) return x;
        // 让负数的桶偏左
        return (x < 0 ? x - width + 1 : x) / width;
    }
}

645. 错误的集合 easy

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

解法 1 标记

java

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        boolean[] vis = new boolean[n];
        int r1 = -1, r2 = -1;
        for (int e : nums) {
            if (vis[e - 1]) r1 = e;
            else vis[e - 1] = true;
        }
        for (int i = 0; i < vis.length; i++) {
            if (!vis[i]) {
                r2 = i + 1;
                break;
            }
        }
        return new int[]{r1, r2};
    }
}

解法 2 交换

将元素 e 映射到索引 e-1 的位置

java

class Solution {
    public int[] findErrorNums(int[] nums) {
        // nums[0] == 1
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) return new int[]{nums[i], i + 1};
        }
        return null;
    }

    private void swap(int[] nums, int i, int j) {
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }
}

高频数

169. 多数元素 easy

剑指 Offer 39. 数组中出现次数超过一半的数字

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

当前元素+1, 非当前元素-1

java

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0;
        Integer aim = null;
        for (int o : nums) {
            if (cnt == 0) aim = o;
            if (o == aim) cnt++;
            else cnt--;
        }
        return aim;
    }
}

347. 前 K 个高频元素 mid

LCR 060. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。

解法 Map+堆

java

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(map::get));
        map.forEach((key, value) -> {
            pq.add(key);
            if (pq.size() > k) pq.remove();
        });
        return pq.stream().mapToInt(o -> o).toArray();
    }
}

594. 最长和谐子序列 easy

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

说是子序列, 其实是求差值为 1 的元素的最多数量

java

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        int res = 0;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            Integer cnt = map.get(e.getKey() - 1);
            if (cnt != null) res = Math.max(res, e.getValue() + cnt);
        }
        return res;
    }
}

第 k 个数

264. 丑数 II mid

剑指 Offer 49. 丑数

给你一个整数 n，请你找出并返回第 n 个丑数。丑数就是只包含质因数 2、3 和/或 5 的正整数。

解法 1 优先队列

java

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> que = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        que.add(1L);
        set.add(1L);
        Long res = null;
        for (int i = 1; i <= n; i++) {
            res = que.remove();
            if (!set.contains(res * 2L)) {
                set.add(res * 2L);
                que.add(res * 2L);
            }
            if (!set.contains(res * 3L)) {
                set.add(res * 3L);
                que.add(res * 3L);
            }
            if (!set.contains(res * 5L)) {
                set.add(res * 5L);
                que.add(res * 5L);
            }
        }
        return res.intValue();
    }
}

解法 2 DP

技巧性很强, 3 根指针, 分别指向需要与 2,3,5 相乘的位置, 每步从 3 个乘积中选最小的, 乘完之后相应的指针+1

java

public class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) p2++;
            if (dp[i] == num3) p3++;
            if (dp[i] == num5) p5++;
        }
        return dp[n];
    }
}

215. 数组中的第 K 个最大元素 mid

给定整数数组 nums 和整数 k，请返回数组中第 k 大的元素。

解法 1 API 排序

时间复杂度 O(NlogN)，空间复杂度 O(1)

java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

解法 2 堆

PriorityQueue 小根堆时间复杂度 O(NlogK)，空间复杂度 O(K)。

Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int val : nums) {
            heap.add(val);
            // remove 小的
            if (heap.size() > k) heap.remove();
        }
        return heap.element();
    }
}

解法 3 快速选择

时间复杂度 O(N)，空间复杂度 O(1)
时间复杂度需要主定理进行分析
快速排序的关键在于找主元 pivot
快速排序选取 pivot 也有技巧, 可以取首中尾 3 个点中的 mid

java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int l = 0, h = nums.length - 1;
        while (true) {
            int pivotIdx = partition(nums, l, h);
            if (pivotIdx < k - 1)
                l = pivotIdx + 1;
            else if (pivotIdx > k - 1)
                h = pivotIdx - 1;
            else return nums[pivotIdx];
        }
    }

    // 重点
    private int partition(int[] arr, int l, int h) {
        int pivot = arr[l];
        int i = l;      // 从 i+1 真正开始
        int j = h + 1;  // 从 h 真正开始
        while (true) {
            while (i < h && arr[++i] > pivot) ;
            while (j > l && arr[--j] < pivot) ;
            // 没有就不交换
            if (i >= j) break;
            swap(arr, i, j);
        }
        // arr[l] 是 pivot, 最终 arr[j] >= pivot, j 右边的元素都小于 pivot
        swap(arr, l, j);
        return j;
    }


    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

400. 第 N 位数字 mid

给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

解法 1 数数

由位数相同的数组成的一层, 每层的位数总和是确定的, 先定位属于哪一层, 再定位是哪个数, 再定位是哪个位

java

class Solution {
    public int findNthDigit(int n) {
        // 定位到哪一层
        int cntDig = 1;
        long cntOfEveryLayer = 9;
        long muti = 1;
        // 1->9, 10->99, 100->999
        while (n > cntOfEveryLayer) {
            n -= cntOfEveryLayer;
            cntDig++;
            muti *= 10;
            cntOfEveryLayer = cntDig * 9 * muti;
        }
        // 剩下的 n 个位定位到哪个数字, 每个数字占 cntDig 个
        long num = muti - 1 + (n + cntDig - 1) / cntDig;
        // 定位哪个位, 1 % 3 = 1, 第1位, 就是[0]
        return Long.toString(num).charAt((n - 1) % cntDig) - '0';
    }
}

解法 2 二分猜答案 略

703. 数据流中的第 K 大元素 mid

LCR 059. 数据流中的第 K 大元素

设计一个找到数据流中第 k 大元素的类(class). 注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

java

class KthLargest {
    PriorityQueue<Integer> pq;
    int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.pq = new PriorityQueue<>();
        for (int e : nums) {
            add(e);
        }
    }

    public int add(int val) {
        pq.add(val);
        if (pq.size() > k) pq.remove();
        return pq.element();
    }
}

前 K 个

373. 查找和最小的 K 对数字 mid

LCR 061. 查找和最小的 K 对数字

给定两个以升序排列的整数数组 nums1 和 nums2, 以及一个整数 k.

定义一对值(u,v), 其中第一个元素来自 nums1, 第二个元素来自 nums2.

请找到和最小的 k 个数对(u1,v1),(u2,v2)...(uk,vk)。

解法堆

top k 只出现在 n1 和 n2 的前 k 个元素中, 取笛卡尔积然后过堆 $O (K^{2} * l o g K)$
如果将 n1[0]与 n2 的前 k 个组合放进堆中，remove 出来的元素对 {n1[0], 与 n2[i]} 之和小于 {n1[1], n2[i]}, 将后者继续放进堆中。
这样会不会漏掉元素对？其实不会，这个添加过程是最优路径，假设 {n1[i], n2[i]} 之和小于 {n1[1], n2[k]}, 那么有 {n1[1], n2[i]} 先于 {n1[1], n2[k]} 进堆。

java

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>(k);
        PriorityQueue<int[]> pq = new PriorityQueue<>(k, Comparator.comparingInt(o -> nums1[o[0]] + nums2[o[1]]));
        // (0,0) -> (k-1,0) 元素对都在里面作为候选
        for (int i = 0; i < Math.min(k, nums1.length); i++) { // 防止越界
            pq.add(new int[]{i, 0});
        }
        while (k-- > 0 && !pq.isEmpty()) { // 防止越界
            int[] idx = pq.remove();
            res.add(List.of(nums1[idx[0]], nums2[idx[1]]));
            if (idx[1] + 1 < nums2.length) // 防止越界
                pq.add(new int[]{idx[0], idx[1] + 1});
        }
        return res;
    }
}

二元组

二元组常用 Map

Map 可以用 array 实现

1. 两数之和 easy

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那 2 个整数，并返回它们的数组下标。
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
You may assume that each input would have exactly one solution, and you may not use the same element twice.

你可以按任意顺序返回答案。
You can return the answer in any order.

JavaGo

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            Integer j = map.get(complement);
            if (j != null) return new int[]{j, i};
            map.put(nums[i], i);
        }
        return null;
    }
}

func twoSum(nums []int, target int) []int {
    m := map[int]int{}
    for i := 0; i < len(nums); i++ {
        gap := target - nums[i]
        j, ok := m[gap]
        if ok {
            return []int{i, j}
        }
        m[nums[i]] = i
    }
    return nil
}

167. 两数之和 II - 输入有序数组 mid

LCR 006. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。
如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int p1 = 0;
        int p2 = numbers.length - 1;
        while (p1 < p2) {
            if ((numbers[p1] + numbers[p2]) == target) break;
            if ((numbers[p1] + numbers[p2]) < target) p1++;
            if ((numbers[p1] + numbers[p2]) > target) p2--;
        }
        return new int[]{p1 + 1, p2 + 1};
    }
}

633. 平方数之和 mid

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 $a^{2} + b^{2} = c$ 。

解法 1 双指针

java

class Solution {
    public boolean judgeSquareSum(int c) {
        int a = 0;
        int b = (int) Math.sqrt(c);
        while (a <= b) {
            int sum = a * a + b * b;
            if (sum == c) return true;
            else if (sum < c) a++;
            else b--;
        }
        return false;
    }
}

解法 2 费马平方和定理

略

三元组

15. 三数之和 mid

LCR 007. 三数之和

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 的三元组。
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

注意：答案中不可以包含重复的三元组。
Notice that the solution set must not contain duplicate triplets.

先排序, 然后从头到尾遍历选定第 0 个元素, 然后双指针选择另外 2 个元素
双指针只选第一个进行去重, 跟前一个相等的跳过

javago

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        // nums[i] <= 0 可以减少扫描数量
        for (int i = 0; i < n && nums[i] <= 0; i++) {
            if (i > 0 && nums[i - 1] == nums[i]) continue;
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    res.add(List.of(nums[i], nums[j], nums[k]));
                    // j < k 完全能够保证不会越界
                    while (j < k && nums[j] == nums[j + 1]) j++;
                    while (j < k && nums[k] == nums[k - 1]) k--;
                    j++;
                    k--;
                } else if (sum < 0)
                    j++;
                else
                    k--;
            }
        }
        return res;
    }
}

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i, e := range nums {
        if e > 0 {
            break
        }
        if i > 0 && e == nums[i-1] {
            continue
        }
        l, r := i+1, len(nums)-1
        for l < r {
            sum := e + nums[l] + nums[r]
            if sum == 0 {
                res = append(res, []int{e, nums[l], nums[r]})
                for ; l+1 < r && nums[l] == nums[l+1]; l++ {}
                for ; l < r-1 && nums[r] == nums[r-1]; r-- {}
                l++
                r--
            } else if sum < 0 {
                l++
            } else {
                r--
            }
        }
    }
    return res
}

923. 三数之和的多种可能 mid

给定一个整数数组 arr，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。

由于结果会非常大，请返回 1E9 + 7 的模。

3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300

解法 1 三数之和+数学

java

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        long res = 0;
        int mod = 1_000_000_007;
        long[] cnt = new long[101];
        for (int num : arr) {
            ++cnt[num];
        }
        if (target == 0) return (int) (cnt[0] * (cnt[0] - 1) * (cnt[0] - 2) / 6 % mod);

        for (int k = 1; k < cnt.length; k++) {
            if (cnt[k] == 0) continue;
            int i = 0, j = k;
            while (i <= j) {
                if (cnt[i] == 0) {
                    i++;
                    continue;
                }
                if (cnt[j] == 0) {
                    j--;
                    continue;
                }
                if (i + j + k == target) {
                    if (i == j && j == k)
                        res = (res + cnt[k] * (cnt[k] - 1) * (cnt[k] - 2) / 6) % mod;
                    else if (j == k)
                        res = (res + cnt[k] * (cnt[k] - 1) / 2 * cnt[i]) % mod;
                    else if (i == j)
                        res = (res + cnt[i] * (cnt[i] - 1) / 2 * cnt[k]) % mod;
                    else
                        res = (res + cnt[k] * cnt[i] * cnt[j]) % mod;
                    ++i;
                    --j;
                } else if (i + j + k < target) ++i;
                else --j;
            }
        }
        return (int) res;
    }
}

解法 2 背包

java

class Solution {

    int mod = 1_000_000_007;

    public int threeSumMulti(int[] arr, int target) {
        int n = arr.length;
        //dp[i][j][k]表示前i个数，从中选出j个数，组成k大小的方案数
        int[][][] dp = new int[n + 1][4][target + 1];
        for (int i = 0; i < n; i++) dp[i][0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 3; j++) {
                for (int k = 0; k <= target; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (k >= arr[i - 1]) {
                        dp[i][j][k] += dp[i - 1][j - 1][k - arr[i - 1]];
                        dp[i][j][k] %= mod;
                    }
                }
            }
        }
        return dp[n][3][target];
    }
}

集合相等

242. 有效的字母异位词 easy

LCR 032. 有效的字母异位词

给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

java

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] arr = new int[26];

        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            if (--arr[t.charAt(i) - 'a'] < 0) return false;
        }
        return true;
    }
}

438. 找到字符串中所有字母异位词 mid

LCR 015. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

解法滑窗

固定窗口中比较集合是否相等

java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length(), m = p.length();
        if (n < m) return new ArrayList<>();
        int[] ap = new int[26];
        int[] aw = new int[26];
        for (int i = 0; i < m; i++) {
            ap[p.charAt(i) - 'a']++;
            aw[s.charAt(i) - 'a']++;
        }

        List<Integer> res = new ArrayList<>();
        for (int i = m - 1; i < n; i++) {
            int idx = i - (m - 1);
            if (Arrays.equals(ap, aw)) res.add(idx);
            if (i == n - 1) break;
            aw[s.charAt(idx) - 'a']--;
            aw[s.charAt(i + 1) - 'a']++;
        }
        return res;
    }
}

分组

49. 字母异位词分组 mid

LCR 033. 字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        for (String str : strs) {
            m.computeIfAbsent(sign(str), o -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(m.values());
    }

    String sign(String s) {
        int[] arr = new int[26];
        for (char c : s.toCharArray()) {
            arr[c - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            int e = arr[i];
            if (e > 0) sb.append((char) ('a' + i)).append(e);
        }
        return sb.toString();
    }
}

416. 分割等和子集 mid

剑指 Offer II 101. 分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

解法背包

dp[i][j] 表示是否存在 1 种方案, 从 nums[0,i] 内选择若干元素, 使被选的正整数和 == j
用连续的整型 idx 去表征背包体积(元素和)

java

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) return false;
        int max = nums[0];
        int sum = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, num);
        }
        if (sum % 2 == 1) return false;
        int half = sum >> 1;
        if (max > half) return false;

        boolean[][] dp = new boolean[n][half + 1];
        dp[0][0] = true;
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            dp[i][0] = true;
            for (int j = 1; j <= half; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i]) dp[i][j] |= dp[i - 1][j - nums[i]];
            }
        }
        return dp[n - 1][half];
    }
}

压缩

压缩是节省空间的技巧, 枚举每个元素, 看最后能否满足 half 空间被恰好填满

java

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int max = Arrays.stream(nums).max().getAsInt();
        if (sum % 2 == 1) return false;
        int half = sum >> 1;
        if (max > half) return false;

        boolean[] dp = new boolean[half + 1];
        dp[0] = true;
        // 因为满足条件的组合里每个元素都是贡献, 不必担心顺序问题
        for (int num : nums) {
            // 因为 dp[j - num] 得晚更新, 否则循环会覆盖; 相当于1个元素重复使用
            for (int j = half; j >= num; j--) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[half];
    }
}

839. 相似字符串组 hard

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

java

class Solution {
    static class UnionFind {

        int[] parent;

        public UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        private int find(int i) {
            if (parent[i] != i)
                parent[i] = find(parent[i]);
            return parent[i];
        }

        private void union(int i, int j) {
            int p1 = find(i);
            int p2 = find(j);
            if (p1 != p2) parent[p2] = p1;
        }
    }

    public int numSimilarGroups(String[] dic) {
        int n = dic.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (check(dic[i], dic[j])) uf.union(i, j);
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (uf.find(i) == i) res++;
        }
        return res;
    }


    private boolean check(String s1, String s2) {
        if (Objects.equals(s1, s2)) return true;
        int n = s1.length();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (cnt > 2) return false;
            if (s1.charAt(i) != s2.charAt(i)) cnt++;
        }
        return cnt == 2;
    }
}

没有重复元素

318. 最大单词长度乘积 mid

LCR 005. 最大单词长度乘积

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j])的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0。

用二进制数字表示集合

解法 1 存储每个 word 的 mask

java

class Solution {
    public int maxProduct(String[] words) {
        int[] arr = new int[words.length];
        int idx = 0;
        for (String word : words) {
            for (char c : word.toCharArray()) {
                arr[idx] |= (1 << c - 'a');
            }
            idx++;
        }
        int max = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((arr[i] & arr[j]) == 0)
                    max = Math.max(max, words[i].length() * words[j].length());
            }
        }
        return max;
    }
}

解法 2 相同 mask 保留最长长度

java

class Solution {
    public int maxProduct(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        for (String word : words) {
            int mask = 0;
            for (char c : word.toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            map.merge(mask, word.length(), Math::max);
        }
        int res = 0;
        for (var e1 : map.entrySet()) {
            for (var e2 : map.entrySet()) {
                if ((e1.getKey() & e2.getKey()) == 0)
                    res = Math.max(res, e1.getValue() * e2.getValue());
            }
        }
        return res;
    }
}

其他

409. 最长回文串 easy

给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

java

class Solution {
    public int longestPalindrome(String s) {
        int[] cnt = new int[128];
        for (char c : s.toCharArray()) {
            cnt[c]++;
        }
        int res = 0;
        for (int i : cnt) {
            res += i / 2 * 2;
        }
        if (s.length() > res) res++;
        return res;
    }
}

最小差值

539. 最小时间差 mid

LCR 035. 最小时间差

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

解法 1 排序

java

class Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 1440) return 0;
        // 00:00 -> 23:59
        int n = timePoints.size();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            String s = timePoints.get(i);
            arr[i] = Integer.parseInt(s.substring(0, 2)) * 60 + Integer.parseInt(s.substring(3, 5));
        }
        Arrays.sort(arr);
        int res = arr[0] + 24 * 60 - arr[arr.length - 1];
        for (int i = 1; i < arr.length; i++) {
            res = Math.min(res, arr[i] - arr[i - 1]);
        }
        return res;
    }
}

解法 2 桶排序

java

class Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 1440) return 0;
        // 00:00 -> 23:59
        boolean[] arr = new boolean[24 * 60];
        int max = 0;
        for (String point : timePoints) {
            int minute = Integer.parseInt(point.substring(0, 2)) * 60 + Integer.parseInt(point.substring(3, 5));
            if (arr[minute]) return 0;
            arr[minute] = true;
            max = Math.max(minute, max);
        }
        int last = max - 1440;
        int res = 1440;
        for (int i = 0; i < arr.length; i++) {
            if (!arr[i]) continue;
            res = Math.min(res, i - last);
            last = i;
        }
        return res;
    }
}

集合中的元素 ​

出现 1 次的数 ​

136. 只出现一次的数字 easy ​

260. 只出现一次的数字 III mid ​

387. 字符串中的第一个唯一字符 easy ​

缺失的数 ​

41. 缺失的第一个正数 hard ​

268. 丢失的数字 easy ​

448. 找到所有数组中消失的数字 easy ​

重复数 ​

287. 寻找重复数 mid ​

217. 存在重复元素 easy ​

36. 有效的数独 mid ​

220. 存在重复元素 III hard ​

645. 错误的集合 easy ​

高频数 ​

169. 多数元素 easy ​

347. 前 K 个高频元素 mid ​

594. 最长和谐子序列 easy ​

第 k 个数 ​

264. 丑数 II mid ​

215. 数组中的第 K 个最大元素 mid ​

400. 第 N 位数字 mid ​

703. 数据流中的第 K 大元素 mid ​

前 K 个 ​

373. 查找和最小的 K 对数字 mid ​

二元组 ​

1. 两数之和 easy ​

167. 两数之和 II - 输入有序数组 mid ​

633. 平方数之和 mid ​

三元组 ​

15. 三数之和 mid ​

923. 三数之和的多种可能 mid ​

集合相等 ​

242. 有效的字母异位词 easy ​

438. 找到字符串中所有字母异位词 mid ​

分组 ​

49. 字母异位词分组 mid ​

416. 分割等和子集 mid ​

839. 相似字符串组 hard ​

没有重复元素 ​

318. 最大单词长度乘积 mid ​

其他 ​

409. 最长回文串 easy ​

最小差值 ​

539. 最小时间差 mid ​

集合中的元素

出现 1 次的数

136. 只出现一次的数字 easy

260. 只出现一次的数字 III mid

387. 字符串中的第一个唯一字符 easy

缺失的数

41. 缺失的第一个正数 hard

268. 丢失的数字 easy

448. 找到所有数组中消失的数字 easy

重复数

287. 寻找重复数 mid

217. 存在重复元素 easy

36. 有效的数独 mid

220. 存在重复元素 III hard

645. 错误的集合 easy

高频数

169. 多数元素 easy

347. 前 K 个高频元素 mid

594. 最长和谐子序列 easy

第 k 个数

264. 丑数 II mid

215. 数组中的第 K 个最大元素 mid

400. 第 N 位数字 mid

703. 数据流中的第 K 大元素 mid

前 K 个

373. 查找和最小的 K 对数字 mid

二元组

1. 两数之和 easy

167. 两数之和 II - 输入有序数组 mid

633. 平方数之和 mid

三元组

15. 三数之和 mid

923. 三数之和的多种可能 mid

集合相等

242. 有效的字母异位词 easy

438. 找到字符串中所有字母异位词 mid

分组

49. 字母异位词分组 mid

416. 分割等和子集 mid

839. 相似字符串组 hard

没有重复元素

318. 最大单词长度乘积 mid

其他

409. 最长回文串 easy

最小差值

539. 最小时间差 mid