代码随想录算法训练营第十一天|383. 赎金信， 15. 三数之和
文档讲解：代码随想录
难度：easy
383. 赎金信
力扣题目链接(opens new window)
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
思路：
因为题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。
步骤如下：
- 将ransomNote和magazine长度比较（magazine一定更长，因为ransomNote的元素都包含在中magazine，故ransomNote是magazine的真子集），如果magazine一定更长继续进行下面的操作，否则返回false
- 创建一个哈希映射数组record将magazine和ransomNote通过ToCharArray( )的用法，将字符串对象中的字符转换为一个字符数组。
- 再通过
record[c - 'a'] += 1;统计magazine和ransomNote中的a到z的有无及个数 - 最后将a到z的有无及个数比较就可以完成。
补充1：
ToCharArray( )的用法，将字符串对象中的字符转换为一个字符数组。
详解释就是：
字符串转换成字符数组后，每个字符的ASC码与字符T的ASC码进行二进制异或运算。
最后把结果转换回字符。
这个和foreach的for循环一样的，也就是遍历
这里的for(char c:chars)就是定义一个遍历字符c，让它分别等于字符串数组chars里面的各个字符，然后执行下面的语句，当c被赋值为chars里面所有字符各一次后，就会退出这个循环.
补充2：
record[c - 'a'] += 1;：在循环体内，这行代码用于更新record数组中对应字符c的计数。这里的关键在于理解c - 'a'这个表达式。由于c是一个字符变量，且假设它代表一个小写字母（'a'到'z'），c - 'a'的结果就是这个字符相对于字母'a'的偏移量。例如，如果c是'b'，那么c - 'a'的结果是1，因为'b'在字母表中是'a'之后的第一个字母。
record数组的大小通常是26（对应于26个小写英文字母），并且每个索引位置代表一个字母的计数。因此，record[0]代表'a'的计数，record[1]代表'b'的计数，依此类推，直到record[25]代表'z'的计数。通过
record[c - 'a'] += 1;，我们找到c对应的数组索引，并将该位置的计数增加1。这样，当循环结束时，record数组中的每个元素都存储了对应字母在magazine字符串中出现的次数。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// shortcut
if (ransomNote.length() > magazine.length()) {
return false;
}
// 定义一个哈希映射数组
int[] record = new int[26];
// 遍历
for(char c : magazine.toCharArray()){
record[c - 'a'] += 1;
}
for(char c : ransomNote.toCharArray()){
record[c - 'a'] -= 1;
}
// 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
for(int i : record){
if(i < 0){
return false;
}
}
return true;
}
}第15题. 三数之和
力扣题目链接(opens new window)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
视频：《代码随想录》算法视频公开课 (opens new window)：梦破碎的地方！| LeetCode：15.三数之和
思路1：
- 创建一个存【int类型数据的列表】类型数据的列表，
- 将数组从小到大排序
- 进入循环：先判断每次三元组的第一个元素是不是>0（数组为排序后，故如果三元组第一个元素大于0那么就不可能符合要求），如果是则结束程序
- 对nums[i]去重（题目要求：注意：答案中不可以包含重复的三元组。）
- 创建一个集合set
- 对nums[j]去重
- 因为0=a+b+c，故c=0-a-b。
- contains方法判断是否符合，如果符合返回true，进入循环体将给定的元素列表转换为一个固定大小的列表加入set
- 最后通过remove(c)去重
补充：
步骤1
List<List>的作用List指的是存int类型数据的列表，List<List>指的是存【int类型数据的列表】类型数据的列表------就是这个母列表存子列表，其子列表存int类型的数据。
步骤2
常规一个数组参数，将数组从小到大排序，时间复杂度为o(nlog n)
Arrays.sort(nums);
步骤3
i > 0：这个条件确保当前索引i不是数组的第一个元素。因为我们要比较nums[i]和nums[i - 1]，如果i是 0，那么nums[i - 1]将尝试访问数组的-1索引，这是非法的。
步骤4
nums[i] == nums[i - 1]：这个条件检查当前元素nums[i]是否与前一个元素nums[i - 1]相等。如果相等，那么可能意味着在搜索满足特定条件（如三个数之和为零）的三元组时，我们会遇到重复的组合。
步骤3，4
如果上述两个条件都满足，即
i > 0且nums[i] == nums[i - 1]，则执行continue语句。continue语句会导致当前迭代立即结束，并继续下一次迭代（即下一个i的值）。这意味着，对于满足条件的当前元素nums[i]，循环体内的剩余代码将不会被执行。
步骤3，4
continue语句可以将程序的控制权移到循环的末尾以去重复
步骤7
Java中的contains方法是一个用于检测字符串中是否包含指定子字符串的实用工具。与indexOf方法类似，它的核心功能是查找子字符串在原字符串中的位置，但有所不同。当调用abcdefg.contains("c")时，它会返回一个布尔值，指示"c"是否存在于"abcdefg"中，结果为true。相反，abcdefg.indexOf("c")则会返回子字符串"c"在主字符串中的起始索引，这里是2，如果找不到则返回-1。因此，contains方法更直观地回答了我们是否找到了特定的子字符串，而indexOf则提供了子字符串的具体位置信息。
步骤8
Arrays.asList(...)：这是一个静态方法，用于将给定的元素列表转换为一个固定大小的列表。在这个场景中，它用于创建一个包含三个元素（nums[i],nums[j],c）的列表。
步骤9
remove()方法是Set接口中的一个方法，通过它可以删除Set集合中指定的元素。具体语法如下：
boolean remove(Object o)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// 如果第一个元素大于零，不可能凑成三元组
if (nums[i] > 0) {
return result;
}
// 三元组元素a去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
HashSet<Integer> set = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
// 三元组元素b去重
if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) {
continue;
}
int c = -nums[i] - nums[j];
if (set.contains(c)) {
result.add(Arrays.asList(nums[i], nums[j], c));
set.remove(c); // 三元组元素c去重
} else {
set.add(nums[j]);
}
}
}
return result;
}
}思路2：双指针
大体与思路1一致，
将left定义为num[i]的下一个，right定义为最后一个，while是将两个指针向中间移动，
由于right较大，故如果sum大于0，则right-1；如果sum小于0，left+1；如果sum等于0，则返回思路1的步骤8后半部分。
再进行left和right的去重
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.length; i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (right > left) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
}