454.四数相加II
文字讲解：四数相加Ⅱ
视频讲解：学透哈希表，map使用有技巧！
题设：给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
难点：暴力解法易超时。
思路：定义哈希映射，表示1、2两个数组的和与出现次数；去查找3、4两个数组其能够匹配1、2数组的和。本题不用去重，所以用映射解决，有一道近似题需要去重，则不能使用这种方法。
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
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 i : nums3) {
for (int j : nums4) {
if (map.containsKey(0 - i - j)) {
count += map.getOrDefault(0 - i - j, 0);
}
}
}
return count;
}
易错点：哈希映射的初始value需要定义，采用getOrDefault方法。
复杂度分析：
- 时间复杂度: O(n^2)。
- 空间复杂度: O(n^2)，最坏情况下A和B的值各不相同。
383. 赎金信
文字讲解：赎金信
题设：给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
难点：非常类似字母异位题，掌握的好的话，本题无难度。
思路：26个字母出现次数，哈希数组解决。
public boolean canConstruct(String ransomNote, String magazine) {
int[] array = new int[26];
for (char c : magazine.toCharArray()) array[c - 'a'] += 1;
for (char c : ransomNote.toCharArray()) {
if (--array[c - 'a'] < 0) return false;
}
return true;
}
复杂度分析：
- 时间复杂度: O(n)。
- 空间复杂度: O(1)。
15. 三数之和
文字讲解：三数之和
视频讲解：梦破碎的地方！
题设：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
难点：去重细节较多。
思路：换一条路走，采用双指针的方法。由于返回的是三元组，而不是下标，所以先进行排序。i起始位置，left和right指针控制与0相比的大小。
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
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) {
right--;
} else if (sum < 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、left、right的去重方式。continue是结束本次循环，开始下一轮。以及Arrays相关的方法。
复杂度分析：
- 时间复杂度: O(n^2)。
- 空间复杂度: O(1)。
18. 四数之和
文字讲解：四数之和
视频讲解：难在去重和剪枝！
题设：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n-
a、b、c和d互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target
难点：与四数相加有区别，去重难度高。
思路：双指针方法，其实类似于三数之和。剪枝操作需要额外注意。
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// nums[i] > target 直接返回, 剪枝操作
if (nums[i] > 0 && nums[i] > target) {
return result;
}
if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
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]));
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return result;
易错点：剪枝时，由于数组内可以有负值，单纯的判断条件不能只是比较与target的大小，也需要判断正负。
复杂度分析：
- 时间复杂度: O(n^3)。
- 空间复杂度: O(1)。
