454.四数相加II
题目链接：454.四数相加II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰四数相加II
日期：2024-09-03
想法：4个数组，两两分开遍历时间复杂度低点，用一个map，key是i+j的值，value是出现次数，对nums3、4只需要判断0 - k - l在不在map里，最后依次加上出现次数就行了。
Java代码如下：
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int count = 0;
for(int i : nums1){
for(int j :nums2){
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
for(int k : nums3){
for(int l : nums4){
count += map.getOrDefault((0 - k - l), 0);
}
}
return count;
}
}
总结：map.getOrDefault(sum, 0)：如果 map 中存在键 sum，则返回该键对应的值；如果不存在，则返回默认值0。
383. 赎金信
题目链接：383. 赎金信
文档讲解︰代码随想录(programmercarl.com)
日期：2024-09-03
想法：比较简单的一题，看到小写字母想到用数组做哈希，接下来就是先遍历magazine做加法，再ransomNote做减法。
Java代码如下：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] record = new int[26];
for (char i : magazine.toCharArray()) {
record[i -'a'] ++;
}
for (char j : ransomNote.toCharArray()) {
record[j - 'a']--;
if(record[j -'a'] < 0) {
return false;
}
}
return true;
}
}
总结： for (char i : magazine.toCharArray())注意这个遍历的方法。
15. 三数之和
题目链接：15. 三数之和
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰三数之和
日期：2024-09-03
想法：1.哈希：两层for循环确定a和b值，再确定 0-a-b是否出现，但去重操作很麻烦；2.双指针：其实感觉是三指针，i为起始点，left = i + 1，right = nums.length - 1，通过判断三个的和与0的大小来压缩空间，这还需要数组本身是有序的，找到和为0的三元组
Java代码如下：
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){
if((nums[i] + nums[left] + nums[right]) > 0){
right--;
}else if((nums[i] + nums[left] + nums[right]) < 0){
left++;
}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;
}
}
总结：这道题中去重是需要头脑很清晰的，从i > 0 && nums[i] == nums[i - 1]，到while (right > left && nums[right] == nums[right - 1]) right--，while (right > left && nums[left] == nums[left + 1]) left++;的位置和方式是right - 1还是right + 1一定要想清楚。
18. 四数之和
题目链接：18. 四数之和
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰四数之和
日期：2024-09-03
想法：思路跟三数之和差不多了，nums[i]的值固定变成nums[k] + nums[i]的固定
Java代码如下：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int k = 0; k < nums.length; k++) {
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.length; i++) {
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (right > left) {
long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[k], 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;
}
}
总结：可以进行些剪枝操作，5数之和到n数之和都可以这个方法，用双指针降低一个复杂度。
if (nums[k] > target && nums[k] >= 0) {
break;
}
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}