我要评论3.4
两数之和
哈希法
为什么会想到用哈希表：当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
-
数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
-
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
-
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。
-
设立map(数据元素，对应下标)，在map中没有这个元素a，就添加进来，然后遍历去寻找map中有没有目标元素target-a
-
设立输出结构、检查输入是否合法
-
设立hashmap，（key：放目标元素 与 value：目标元素索引）遍历输入：
-
当前i，如果hashmap中有target-i，就返回i和target-i的value
-
如果没有，就把i添加到hashmap
-
class solution {
public int[] twosum(int[] nums, int target) {
int res[] = new int[2];
if (nums == null || nums.length == 0){
return res;
}
map<integer,integer> nums_map = new hashmap<>();
// 设立hashmap，（key：放目标元素 与 value：目标元素索引）遍历输入：
for(int i = 0; i<nums.length; i++){
int nums_j = target - nums[i];
// 当前i，如果hashmap中有target-i，就返回i和target-i的value
if(nums_map.containskey(nums_j)){
res[0] = i;
res[1] = nums_map.get(nums_j);
// res[1] = nums_map(nums_j).value; 如果你想通过键来获取值，你应该使用get方法，而不是尝试使用nums_map(nums_j).value;这样的语法。hashmap没有提供直接通过属性访问其内部数据的方式
break; //一旦if条件满足，并且执行了break语句，就会立即跳出for循环。添加break语句在这个场景中是有必要的。一旦你在循环中找到满足条件的一对索引（即，数组中存在两个数的和等于目标值target），你就已经找到了问题的答案，此时没有必要继续遍历数组。break语句的作用是立即终止循环，这样可以避免执行不必要的迭代，从而提高代码的效率。
}
// 如果没有，就把i添加到hashmap
// nums_map.add(nums[i],i); put()方法接受两个参数，第一个参数是键，第二个参数是值，这里的键是数组中的元素nums[i]，而值是该元素的索引i。add()方法并不是hashmap类的一部分
nums_map.put(nums[i], i);
}
return res;
}
}注意细节
-
需要使用
get、put等api方法来操作hashmap的内容get(nums_j)方法返回的是与这个键相关联的值，即数组nums中与nums_j相对应的元素的索引。语句
res[1] = nums_map.get(nums_j);的含义是将nums_j在原数组中的索引（也就是nums_j对应的值在hashmap中的值）赋给res[1]。 -
注意
break的条件：添加break语句在这个场景中是有必要的。一旦你在循环中找到满足条件的一对索引（即，数组中存在两个数的和等于目标值target），你就已经找到了问题的答案，此时没有必要继续遍历数组。break语句的作用是立即终止循环，这样可以避免执行不必要的迭代，从而提高代码的效率。
四数相加ii
题目：给定四个包含整数的数组列表 a , b , c , d ,计算有多少个元组 (i, j, k, l) ，使得 a[i] + b[j] + c[k] + d[l] = 0。
本题解题步骤：
-
首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
-
遍历大a和大b数组，统计两个数组元素之和，和出现的次数，放到map中。
-
定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
-
在遍历大c和大d数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
-
最后返回统计值 count 就可以了
从map中获取一个sum出现的次数
map.getordefault(sum, 0)
class solution {
public int foursumcount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
map<integer,integer> map = new hashmap<>();
for(int i : nums1){
for(int j : nums2){
int sum = i + j;
// hashmap:key,value。放加和与加和出现的次数
map.put( sum, map.getordefault(sum,0)+1);
}
}
for(int k:nums3){
for(int l:nums4){
int target = 0 - k - l;
// target是否有出现（使加和为0）
res += map.getordefault(target,0);
// 统计出现次数res
}
}
return res;
}
}-
四个数加和为0也就是
前两个数加和 + 后两个数加和 = 0，所以统计前两个数加和 = 0 - 后两个数加和成立出现的次数 -
map.getordefault(sum, 0)：如果存在返回sum出现的次数，如果不存在返回0
赎金信
题目：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点。
-
第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
-
第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要
但是本题中int[] record = new int[26];并不是定义一个哈希映射数组，而是定义了一个整数型数组，其大小为26。这个数组的用途通常是为了记录每个英文字母出现的次数，这种做法在处理只包含小写英文字母的字符串问题时非常常见。
这里的26代表英文字母表中的字母数量，即从'a'到'z'的26个字母。每个数组元素的索引对应于特定字母在字母表中的位置。例如，索引0对应于字母'a'，索引1对应于字母'b'，以此类推，直到索引25，它对应于字母'z'。
使用这种方法，你可以通过简单的算术操作将字符转换为索引（例如，char - 'a'）来增加或减少特定字母的出现次数。例如，如果你想记录字母'a'的出现次数，你可以做如下操作：
record['a' - 'a']++; // 增加字母'a'的计数
这种方法非常适合于处理字符频率相关的问题，因为它提供了一种简单且高效的方式来统计每个字母的出现次数，而无需使用哈希映射（hashmap）。这种数组的方法在空间和时间效率上通常优于哈希映射，尤其是在涉及大量数据的情况下，因为它避免了哈希映射的额外开销（如计算哈希值和处理哈希冲突）。
定义一个数组映射字母；统计magazine字母出现次数，然后遍历ransomnote统计字母出现次数相减，如果为负则有不存在的字。
遍历取字母出现次数
for(char c : magazine.tochararray()){
record[c - 'a'] += 1;
}
class solution {
public boolean canconstruct(string ransomnote, string magazine) {
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;
}
for(int i: record){
if(i<0){
return false;
}
}
return true;
}
}注意细节
-
对于string要
ransomnote.length()而不是ransomnote.length-
对于数组，使用
.length属性来获取数组的长度。 -
对于字符串，使用
.length()方法来获取字符串的长度。
-
-
magazine.tochararray()方法是string类的一个方法，用于将字符串对象转换成一个字符数组。这个方法会返回一个新的字符数组，数组中的每个元素都是字符串中对应位置的字符。
三数之和
题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
哈希解法（很慢）
import java.util.arraylist;
import java.util.arrays;
import java.util.hashset;
import java.util.list;
import java.util.set;
class solution {
public list<list<integer>> threesum(int[] nums) {
set<list<integer>> res = new hashset<>(); // 使用set防止重复
if (nums.length < 3) return new arraylist<>(res); // 数组长度小于3，直接返回
arrays.sort(nums); // 排序
for (int i = 0; i < nums.length - 2; i++) {
set<integer> set = new hashset<>();
for (int j = i + 1; j < nums.length; j++) {
int complement = -nums[i] - nums[j];
if (set.contains(complement)) {
list<integer> triplet = arrays.aslist(nums[i], nums[j], complement);
res.add(triplet); // 添加到结果集，hashset会自动去重
} else {
set.add(nums[j]);
}
}
}
return new arraylist<>(res); // 转换为列表返回
}
}双指针
其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。
创建一个列表的列表
list<list<integer>> result = new arraylist<>(); // 其中每个元素都是一个整数列表（list<integer>）。这种数据结构通常用来存储一组元素，其中每个元素本身也是一组元素。
arrays.sort(nums); // 排序数组
去重
if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
continue; // 如果当前元素与前一个元素相同，则跳过当前元素以避免重复的三元组。
}
找到三元组，去重并添加到结果集
result.add(arrays.aslist(nums[i], nums[left], nums[right]));
-
arrays.aslist(nums[i], nums[left], nums[right])创建了一个包含三个元素的列表，这三个元素分别是nums[i]、nums[left]和nums[right]。这三个元素是当前迭代中找到的和为0的三元组。 -
result.add(...)将这个三元组列表添加到result列表中。result是一个list<list<integer>>类型的对象，用来存储所有找到的符合条件的三元组。
result.add(arrays.aslist(nums[i], nums[left], nums[right])); while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; right--; left++;
class solution {
public list<list<integer>> threesum(int[] nums) {
list<list<integer>> res = new arraylist<>();
arrays.sort(nums);
for(int i=0; i< nums.length;i++){
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
// 去重i
if(i>0 && nums[i] == nums[i-1]) continue; // 写上i>0有必要因为防止数组越界
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{
res.add(arrays.aslist(nums[i],nums[left],nums[right]));
while(right>left && nums[right]==nums[right-1]) right--;
while(right>left && nums[left]==nums[left+1]) left++;
// 要继续移动因为可能有其他可能的组合
right--;
left++;
}
}
}
return res;
}
}注意细节
-
这个题目不需要返回数组索引，所以可以使用双指针法时的排序
-
在java中，如果
while循环体或者任何其他控制流语句（如if、for等）只包含一条语句，那么大括号{}是可以省略的。 -
if(i>0 && nums[i] = nums[i-1]) continue;写上i>0有必要因为防止数组越界 -
注意
int i=0 -
注意返回结果
return res;
四数之和
题目：题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
去重
这种去重方法的关键在于，它只跳过了作为相同起点的重复元素，而不是跳过所有重复元素的所有可能组合。只要有一个组合的起点被考虑，与这个起点相关的所有有效组合（即使包含重复元素）都会被探索。
if(i > 0 && nums[i] == nums[i-1]) continue;
加和的结果
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
class solution {
public list<list<integer>> foursum(int[] nums, int target) {
list<list<integer>> res = new arraylist<>();
arrays.sort(nums);
// 从左往右选第一个数
for(int i = 0;i < nums.length-3;i++){
// 如果第一个数已经大于target就没必要再继续了
if(nums[i]>0 && nums[i] > target) return res;
// i去重
if(i>0 && nums[i] == nums[i-1]) continue;
for(int j = i+1;j < nums.length-2; j++){
if(j>i+1 && nums[j] == nums[j-1]) continue;
int left = j + 1;
int right = nums.length -1;
while(left<right){
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if(sum>target){
right--;
}else if(sum<target){
left++;
}else{
res.add(arrays.aslist(nums[i],nums[j],nums[left],nums[right]));
while(right>left && nums[left]==nums[left+1])left++;
while(right>left && nums[right]==nums[right-1])right--;
left++;
right--;
// 当sum == target时，即找到一个符合条件的四元组后，代码中同时移动left和right指针的做法是为了继续寻找其他可能的组合。在这一步之前，已经将当前找到的组合添加到结果集中了。然后，为了避免重复的组合被再次添加，代码使用两个while循环分别向后和向前移动left和right指针，跳过所有与当前left和right指向的数值相同的数。这种做法确实可能让人担心是否会错过某些有效的组合，尤其是在只需要移动left或只需要移动right的情况下。但事实上，由于数组已经排序，这种方法是有效且安全的。
}
}
}
}
return res;
}
}注意细节
-
剪枝的位置应该是迭代
i时，计算数据段判断开头的数据是否大于target -
加和的结果防止溢出要用
long -
去重的时候：
if(i > 0 && nums[i] == nums[i-1]) continue;
-
遍历四个数的第一个数时
for(int i = 0;i < nums.length-3;i++)，不要忘记其在第一个位置后面应该还有至少3个数 -
剪枝的时候，要限定第一个数大于零的情况，防止误操作
哈希表的 数组、set 和 map 要灵活运用
发表评论