掌握情况

题目 通关
有效的字母异位词 通过
两个数组的交集 通过（Set API 需要熟悉）
快乐数 通过（链表是否有环）
两数之和 通过
四数相加Ⅱ 未通过
赎金信 通过
三数之和
四数之和

有效的字母异位词

LeetCode 242.有效的字母异位词

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

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

1
2
输入: s = "anagram", t = "nagaram"
输出: true

排序法

  • t 是 s 的异位词等价于「两个字符串排序后相等」。
  • 因此我们可以对字符串s 和t 分别排序，看排序后的字符串是否相等即可判断。
  • 此外，如果s 和t 的长度不同，t 必然不是s 的异位词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 排序法
public boolean isAnagram(String s, String t) {
    // 长度不相等，之u姐舍弃
    if (s.length() != t.length()) {
        return false;
    }
    // 排序比较
    char[] chars1 = s.toCharArray();
    char[] chars2 = t.toCharArray();

    Arrays.sort(chars1);
    Arrays.sort(chars2);

    return Arrays.equals(chars1, chars2);
}

复杂度分析

O(nlogn)。排序的时间复杂度为 O(nlogn)，比较两个字符串是否相等时间复杂度为O(n)，因此总体时间复杂度为$O(nlogn+n)=O(nlogn)$。排序需要O(logn)的空间复杂度。

哈希法

  • 维护一个长度为26 的频次数组table，先遍历记录字符串s 中字符出现的频次，然后遍历字符串t，减去table 中对应的频次，
  • 如果出现 $table[i]<0$，则说明 t 包含一个不在s 中的额外字符，返回 false 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isAnagram(String s, String t) {
    // 长度不相等，之u姐舍弃
    if (s.length() != t.length()) {
        return false;
    }

    int[] table = new int[26];
    // 统计词频
    for (int i = 0; i < s.length(); i++) {
        table[s.charAt(i) - 'a']++;
    }
    // 遇到一样的字符，对应减去即可
    for (int i = 0; i < t.length(); i++) {
        table[t.charAt(i) - 'a']--;
        if (table[t.charAt(i) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

遇到Unicode字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    Map<Character, Integer> table = new HashMap<Character, Integer>();

    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        table.put(ch, table.getOrDefault(ch, 0) + 1);
    }
    
    for (int i = 0; i < t.length(); i++) {
        char ch = t.charAt(i);
        table.put(ch, table.getOrDefault(ch, 0) - 1);
        if (table.get(ch) < 0) {
            return false;
        }
    }
    return true;
}

两个数组的交集

LeetCode 349.两个数组的交集

问题

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

双指针 + 排序

算法思想

  1. 首先对两个数组进行排序，呈非递减状态
  2. 用pre表示上次加入答案数组的元素
  3. 使用双指针分别指向两个数组，每次两个指针比较指向的位置的值
    • 如果两值不相等，则指向较小的数字的指针右移一位
    • 如果两值相等，且该数组不等于pre，将答案添加，并且双指针右移
    • 当至少一个指针超出数组反问，则遍历结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 双指针 + 排序
public int[] intersection(int[] nums1, int[] nums2) {
    // 排序操作
    Arrays.sort(nums1);
    Arrays.sort(nums2);

    int len1 = nums1.length;
    int len2 = nums2.length;

    int[] ans = new int[len1  + len2];

    int cur = 0, i = 0, j = 0;

    while (i < len1 && j < len2) {
        if (nums1[i] == nums2[j]) {
            if (cur == 0 || nums1[i] != ans[cur - 1]) {
                ans[cur++] = nums1[i];
            }
            i++;
            j++;
        } else  if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return Arrays.copyOfRange(ans, 0, cur);
}

复杂度分析

O(mlogm+nlogn)，其中m和n为数组的长度。对两个数组排序的时间复杂度分别是O(mlogm)和O(nlogn)，双指针寻找交集元素的时间复杂度是O(m+n)，因此总时间复杂度是O(mlogm+nlogn)。

哈希

算法思想

  1. 使用两个集合存储数组元素
  2. 遍历较小集合
  3. 判断该集合元素是否在另一个集合中
  4. 如果在直接加入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 哈希
public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();

    for (int num : nums1) {
        set1.add(num);
    }

    for (int num : nums2) {
        set2.add(num);
    }
    return getInterSection(set1, set2);
}

public int[] getInterSection(Set<Integer> smallSet, Set<Integer> bigSet) {
    // 保持调用形式
    if (smallSet.size() > bigSet.size()) {
        return getInterSection(bigSet, smallSet);
    }

    Set<Integer> ans = new HashSet<>();

    // 遍历小集合
    for (Integer num : smallSet) {
        if (bigSet.contains(num)) {
            ans.add(num);
        }
    }

    // Set-->int[]
    int[] intersection = new int[ans.size()];
    int index = 0;

    for (int el : ans) {
        intersection[index++] = el;
    }
    
    return intersection;
}

复杂度分析

O(m+n)，其中m和n 为数组的长度。存储两个数组需要O(m+n)的时间，遍历较小的集合需要O(min(m,n))的时间

快乐数

LeetCode 202.快乐数

问题

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
    • 如果这个过程 结果为 1，那么这个数就是快乐数。
      如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
1
2
3
4
5
6
7
8
9
10
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

输入：n = 2
输出：false

哈希表

猜测三种情况

  • 最终得到1
  • 最终进入循环
  • 值越来越大，趋于无穷

    表格表示每位数的最大数字的下一位

Digits Largest Next
1 9 81
2 99 162
3 999 243
4 9999 324
13 9999999999999 1053

  • 3位的数字不可能超过243，要么在243以下的循环内，要么跌到1

  • 4位以及4位以上的每走一步丢失一位，直到降到3位为止

  • 最坏的情况下，算法可能会在243以下的所有数字上循环，然后回到它已经到过的一个循环或者回到1。但它不会无限期地进行下去，所以我们排除第三种选择。

算法实现

1.给一个数字 n，它的下一个数字是什么？数位分离，求平方和。
2.按照一系列的数字来判断我们是否进入了一个循环。
使用哈希集合完成。每次生成链中的下一个数字时，我们都会检查它是否已经在哈希集合中。

  • 如果它不在哈希集合中，我们应该添加它。
  • 如果它在哈希集合中，这意味着我们处于一个循环中，因此应该返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int getNext(int n) {
    int totalSum = 0;

    // 对于 19
    // 低 --> 高
    while (n > 0) {
        // digit = 19 % 10 = 9
        int digit = n % 10;

        // n = 19 / 10 = 1
        n = n / 10;
        totalSum += digit * digit;
    }
    return totalSum;
}

public boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    
    //  一旦出现重复的就返回false
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = getNext(n);
    }
    return n == 1;
}

链表有环

反复调用getNext(n)，得到隐式链表，转换成链表是否有环问题

  • 如果n是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。

  • 如果n不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isHappy(int n) {
    int slow = n;
    int fast = getNext(n);

    while (fast != 1 && slow != fast) {
        // slow = slow.next
        slow = getNext(slow);
        
        // fast = fast.next.next
        fast = getNext(getNext(fast));
    }
    return fast == 1;
}

两数之和

LeetCode 1.两数之和

问题

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

暴力枚举

枚举数组中的每一个数 x，寻找数组中是否存在 target - x。当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 暴力枚举
public int[] twoSum(int[] nums, int target) {
    // 哨兵i指向当前待处理的元素，哨兵j用于找出target-nums[i]的元素
    int i, j;
    for (i = 0; i < nums.length; i++) {
        for (j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[]{i, j};
            }
        }
    }

    return new int[0];
}

哈希表

可以建立<值，索引>的哈希映射，遍历数组，遇到元素index将其值和索引加入哈希表，并且判断target-nums[index]是否在哈希表中。如果没有发现继续循环，如果发现了直接返回结果HE

1
2
3
4
5
6
7
8
9
10
11
12
// 哈希表
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            return new int[]{map.get(target - nums[i]), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

四数相加 II

LeetCode 454.四数相加 II

问题

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

算法思想

  1. 将A、B分一组，C、D分一组
  2. 对于A和B，用二重循环遍历，得到所有A[i]+B[j]的值并存入哈希映射
  3. 对于C和D，用二重循环遍历。当遍历到C[k]+D[l]时，如果-(C[k]+D[l])出现在哈希映射中，那么将对应的值累加进答案中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    // 1. 将AB分为一组，CD分为一组
    int ans = 0;
    HashMap<Integer, Integer> mapAB = new HashMap<>();

    // 2. 对于A和B，得到所有A[i]+B[j]的值，映射进哈希表
    for (int i : nums1) {
        for (int j : nums2) {
            // <AB元素和,频次>
            mapAB.put(i + j, mapAB.getOrDefault(i + j, 0) + 1);
        }
    }

    // 3. 对于C和D，计算C[k]+D[l]
    for (int k : nums3) {
        for (int l : nums4) {
            if (mapAB.containsKey(-(k + l))) {
                ans += mapAB.get(-(k+l));
            }
        }
    }
    
    return ans;
}

赎金信

LeetCode 383.赎金信

问题

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

算法思想

要找出magazine中的一些字符能不能构成ransomNote，可以将magazine映射进哈希，然后遍历ransomNote，遇到相同的频次—，如果magazine中出现某些值小于0，说明构成不了ransomNote

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean canConstruct(String ransomNote, String magazine) {

    // 违规条件
    if (ransomNote.length() > magazine.length()) {
        return false;
    }

    // 统计magazine中的词频
    int[] frequency = new int[26];
    for (char ch : magazine.toCharArray()) {
        frequency[ch - 'a']++;
    }
    
    // 遍历ransomNote
    for (char ch : ransomNote.toCharArray()) {
        frequency[ch - 'a']--;
        // 若magazine中某词频不足0，说明缺少字符构成ransom
        if (frequency[ch - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

三数之和

LeetCode 15. 三数之和

问题

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

排序 + 双指针

题目中要求找到所有不重复且和为0的三元组，这个不重复的要求让我们无法简单使用三重循环枚举所有的三元组，最坏情况，数组元素全为0

任意一个三元组的和都为0，如果我们直接使用三重循环枚举三元组世家复杂度至少$O(N^3)$。之后我们还需要使用哈希表去重，空间复杂度又很高

不重复的本质：

  1. 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素
  2. 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素

也就是说，枚举的三元组(a,b,c)满足$a≤b≤c$，保证只有(a,b,c)这个顺序会被枚举到，而(b,a,c)、(c,b,a)都不会，这样就减少重复，实现这点需要进行从小到大的排序
同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。举个例子，如果排完序的数组为[0, 1, 2, 2, 2, 3]
使用三重循环枚举到的第一个三元组为(0,1,2)，如果第三重循环继续枚举下一个元素，那么仍然是该三元组，会产生重复，因此需要将第三重循环跳到下一个不相同的元素，即数组中的最后一个元素，枚举三元组(0,1,3)

1
2
3
4
5
6
7
8
9
10
nums.sort()
for first = 0 .. n-1
    // 只有和上一次枚举的元素不相同，才能进行枚举
    if first == 0 or nums[first] != nums[first-1] then
        for second = first + 1 .. n-1
            if second == first + 1  or nums[second] != nums[second-1] then
                for third = second + 1 .. n-1
                    if third == second + 1 or nums[third] != nums[third-1] then
                        // 判断是否有a+b+c==0
                        check(first, second, third)

该方法时间复杂度还是为$O(N^3)$，如果我们固定了前两重循环枚举到的元素a和b，那么只有唯一的c满足$a+b+c=0$，当第二重循环往后枚举一个元素b'时，由于$b’>b$，那么满足 $a+b’+c’=0$ 的c'一定有 $c’<c$，即c'在数组中一定出现在c的左侧
因此我们可以从小到大枚举b，同时从大到小枚举c，即第二重循环和第三重循环实际是并列关系
可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针

1
2
3
4
5
6
7
8
9
10
11
nums.sort()
for first = 0 .. n-1
    if first == 0 or nums[first] != nums[first-1] then
        // 第三重循环对应的指针
        third = n-1
        for second = first+1 or nums[second] != nums[second-1] then
            // 向左移动指针，直到a+b+c不大于0
            while nums[first]+nums[second]+nums[third] > 0
                third = third - 1
            // 判断是否有 a+b+c==0
            check(first, second, third)    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public List<List<Integer>>  threeSum(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();

    // 枚举a
    for (int first = 0; first < n; ++first) {
        // 需要和上一次枚举的数不同
        if (first > 0 && nums[first] == nums[first - 1]) { // 说明与上次相同
            continue;
        }
        // c对应的指针初始指向数组的最右端
        int third = n - 1;
        int target = -nums[first];
        // 枚举b
        for (int second = first + 1; second < n; ++second) {
            // 需要和上次枚举的数不同
            if (second > first + 1 && nums[second] == nums[second - 1]) { // 说明与上次相同
                continue;
            }
            // 需要保证b指针在c指针的左侧
            while (second < third && nums[second] + nums[third] > target) {
                --third;
            }
            // 如果指针重合，随着b后续的增加
            // 就不会有满足a+b+c=0并且b<c的c了，可以退出循环
            if (second == third) {
                break;
            }
            if (nums[second] + nums[third] == target) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[first]);
                list.add(nums[second]);
                list.add(nums[third]);
                ans.add(list);
            }
        }
    }
    return ans;
}

四数之和

LeetCode 18.四数之和

问题

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
    nums[a] + nums[b] + nums[c] + nums[d] == target

排序 + 双指针

本题与三数之和具有异曲同工之妙，思想相似。

算法思想

为了避免枚举到重复四元组，需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素，且在同一重循环中不能多次枚举到相同的元素

为了实现上述要求，可以对数组进行排序，并在循环中做到以下两点：

  1. 每一种循环枚举到的下标必须大于上一重循环枚举到的下标
  2. 同一重循环中，如果当前元素与上一个元素相同，则跳过当前元素

使用上述方法，可以避免枚举到重复四元组，但是由于使用四重循环复杂度还是比较高，我们采取双指针法优化掉一层循环

使用双重循环分别枚举前两个数，然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。
假设两重循环枚举到的前两个数分别位于下标i和j，其中 $i<j$ 。
初始时，左右指针分别指向下标$j+1$和下标$n-1$。每次计算四个数的和，并进行如下操作：

  • 如果和等于target，则将枚举到的四个数加到答案中，然后将左指针右移直到遇到不同的数，将右指针左移直到遇到不同的数；
  • 如果和小于target，则将左指针右移一位
  • 如果和大于target，则将右指针左移一位

使用双指针枚举剩下的两个数的时间复杂度是$O(n)$，因此总时间复杂度是 $O(n^3)$

继续优化

  • 在确定第一个数之后，如果$nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target$，说明此时剩下的三个数无论取什么值，四数之和一定大于target，因此退出第一重循环；

  • 在确定第一个数之后，如果 $nums[i]+nums[n−3]+nums[n−2]+nums[n−1]<target$，说明此时剩下的三个数无论取什么值，四数之和一定小于target，因此第一重循环直接进入下一轮，枚举nums[i+1]；

  • 在确定前两个数之后，如果$nums[i]+nums[j]+nums[j+1]+nums[j+2]>target$，说明此时剩下的两个数无论取什么值，四数之和一定大于target，因此退出第二重循环；

  • 在确定前两个数之后，如果 $nums[i]+nums[j]+nums[n−2]+nums[n−1]<target$，说明此时剩下的两个数无论取什么值，四数之和一定小于target，因此第二重循环直接进入下一轮，枚举nums[j+1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public List<List<Integer>> fourSum(int[] nums, int target) {

    List<List<Integer>> ans = new ArrayList<>();
    // 违规条件
    if (nums.length < 4 || nums == null) {
        return ans;
    }
    // 排序，满足前提条件
    Arrays.sort(nums);
    int len = nums.length;

    // 第一轮循环 确定第一个数
    for (int i = 0; i < len - 3; i++) {
        // 去重操作
        if (i > 0 && nums[i - 1] == nums[i]) {
            continue;
        }
        // 剪枝操作1
        if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        // 剪枝操作2
        if ((long) nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target) {
            break;
        }

        // 第二轮循环 确定前两个数
        for (int j = 0; j < len - 2; j++) {
            // 去重操作
            if (j > 0 && nums[j - 1] == nums[j]) {
                continue;
            }
            // 剪枝操作3
            if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }
            // 剪枝操作4
            if ((long) nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {
                break;
            }

            // 第三重循环 使用双指针 枚举剩下两个数
            int left = j + 1, right = len - 1;
            while (left < right) {
                // sum
                long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                if (sum == target) {
                    ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    // 将双指针移动到下一个不同数的位置处
                    while (left < right && nums[left + 1] == nums[left]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }

            }

        }
    }
    return ans;
}