383.赎金信https://leetcode.cn/problems/ransom-note/description/
思路：本题与242.有效的字母异位词几乎相同。将字母-'a',变成0-26的数字存放于数组中，再遍历数组对比次数。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] record = new int[26];
for (int i = 0; i < magazine.length(); i++) {
record[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
if (record[ransomNote.charAt(i) - 'a'] == 0) {
return false;
}
record[ransomNote.charAt(i) - 'a']--;
}
return true;
}
}
**-----------------------分割线-------------------------**
454.四数相加IIhttps://leetcode.cn/problems/4sum-ii/description/
思路：暴力解①：对四个数组直接嵌套for循环。暴力解②：分别使用两个结果数组存放数组和，在遍历两个结果数组求等零次数。
优解：本题只需要返回次数，不在意元素是否重复问题，使用map，两个数组和sum作为key，次数作为value，嵌套遍历前两个数组和，统计好所有出现sum次数。再嵌套遍历后两个数组和，对比map中sum和，若相加等零，则int ans++；
重点:理解并使用map.getOrDefault(Object key, V defaultValue)，返回key对应value值，否则返回defaultValue。
map.put(sum,map.getOrDefault(sum,0)+1);实现了在map中将sum出现的次数自增。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int ans = 0;
int sum;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i : nums1) {
for (int j : nums2) {
sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
for (int i : nums3) {
for (int j : nums4) {
sum = -(i + j);
ans += map.getOrDefault(sum, 0);
}
}
return ans;
}
}
**-----------------------分割线-------------------------**
15.三数之和https://leetcode.cn/problems/3sum/
思路：本题较难。
①：建立List<List<Integer>> result用于存放符合条件的数组
②：先将数组排序，使用i遍历，若nums[i]大于0，可直接返回。
③：left = i + 1; right = nums.length - 1;，使用左右双指针，找到符合条件的三数数组，用result存放，若结果大于0，right--，若结果小于0，left++。
④：本题难点在于去重。例如[-1,-1,0,1]，当第一个-1与后面的结果遍历完后，第二个-1可直接跳过，否则会有重复的三元组。同样，[-2,-1,0,3,3]数组中，right在找到一个符合结果的三元组时，也要去重。
去重思路：{
对于i：判断i对应的元素与i-1元素是否相等，若相等可以直接跳过该元素。if (i > 0 && nums[i] == nums[i - 1]) {continue;}
对于left或right：仅在找到符合条件的三元组时需要去重，left右移到第一个与当前值不相等的位置，right左移到第一个与当前值不相等的位置。
while (right > left && nums[right] == nums[right - 1]) {right--;}
while (right > left && nums[left] == nums[left + 1]) {left++;}
}
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int left, right, sum;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
left = i + 1;
right = nums.length - 1;
while (right > left) {
sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
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++;
}
}
}
return result;
}
}
**-----------------------分割线-------------------------**
18.四数之和https://leetcode.cn/problems/4sum/
思路：本题是三数之和的加强版，在i的基础上嵌套一层j的循环遍历，增加j的去重判定。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int left, right, sum;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0 && nums[i] > target) {
return result;
}
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
left = j + 1;
right = nums.length - 1;
while (right > left) {
sum = nums[j] + nums[i] + nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
result.add(Arrays.asList(nums[i], nums[j], 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 result;
}
}
太久没喝奶茶了，今天奖励自己一杯