详细可移步个人代码随想录打卡
四数相加
使用2次，2层for循环。即可确定和值，然后使用一个map来记录第一个for循环的值，再第二次for循环中找，并记录次数即可。
代码如下：
import java.util.HashMap;
import java.util.Map;
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int count = 0;
Map<Integer,Integer> map = new HashMap<>();
for(int i : nums1){
for(int j : nums2){
int sum = i + j;
map.put(sum,map.getOrDefault(sum, 0)+1);
}
}
for(int c : nums3){
for(int d : nums4){
int temp = 0 - c - d;
if(map.containsKey(temp)){
count += map.get(temp);
}
}
}
return count;
}
}
赎金信
该题的思路与字母的有效移位词非常像。可以创建一个数组作为哈希表，存储字母数量，然后遍历另一个字符串，对应字母数-1，如果有小于0的情况就返回false，否则就返回true。
代码如下：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] ransom = new int[26];
for(int i = 0;i < magazine.length();i++){
ransom[magazine.charAt(i)-'a']++;
}
for(int j = 0;j < ransomNote.length();j++){
ransom[ransomNote.charAt(j)-'a']--;
if (ransom[ransomNote.charAt(j)-'a']<0) {
return false;
}
}
return true;
}
}
三数之和
本题的思路使用双指针，首先第一个for循环遍历整个数组，然后在循环中设置两个指针，通过i和两个指针对应的值求和，如果是0就放入result中，然后对左右指针进行去重，大于小于则移动左右指针。遍历前要对数组进行排序。
本题我写的时候有以下问题：
重复的去重逻辑问题：在发现一个合法的三元组后，左右指针都会移动，并再次进行去重操作。其实，只需要在左右指针移动后，进行一次去重操作。
指针移动位置错误：在发现一个合法的三元组后，应该在左右指针去重之后，再移动指针到新的位置。
代码如下：
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
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;
if(i != 0 && nums[i] == nums[i - 1]){
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(right > left){
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
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++;
left++;
right--;
}else if(sum > 0){
right--;
}else if(sum < 0){
left++;
}
}
}
return result;
}
}
四数之和
该题思路与三数之和一样，但是需要注意需要多加一层for循环。其次是剪枝处理需要注意target可能是负数。
此外需要注意的是在循环中注意范围以及左右指针的去重。还有一点，和需要long格式，不然有两个例子通过不了。
代码如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0;i < nums.length-3;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(right > left){
long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
if(sum > target){
right--;
}else if (sum < target){
left++;
}else{
result.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--;
}
}
}
}
return result;
}
}
今日八股
- 一条查询SQL的语句是如何执行的？
- 事物的四大特性有哪些？
- 数据库的事物隔离级别有哪些？