题目链接：454. 四数相加 II
状态：没做出来，看了解析后尝试自己写，但是写的很复杂而且还没写对 - -。最后是照着样例代码敲出来的。学到了不少。最主要是学会了Java8中的map.getOrDefault(key, defaultValue)这个方法，该方法的作用是寻找key，找到了就返回对应的value，没找到就返回defaultValue。
看到题目时第一想法：暴力搜索，时间复杂度O(N^4)。好像即使是有更好的方法，复杂度也降低不了多少。所以就看解析了。
解析的思路是两两数组相加，时间复杂度就由O(N^4)降为O(N^2)，事实上，这已经是很大程度的优化了。具体步骤如下：
- 计算 sum1和sum2 的所有可能的和，然后存入到map中。和作为key，和出现的次数作为value。
- 计算 sum3和sum4 的所有可能的和，然后检查map中是否有对应的相反数。有的话就把计数用的count加上map中的value。
- 最后返回count就好。
完整代码如下： 时间复杂度 和 空间复杂度 均为 O(N^2)
class Solution { // Java
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// Count the sum of the elements in the two arrays,
// count the number of occurrences, and put them into the map
for(int i : nums1){
for(int j : nums2){
int sum = i + j;
map.put(sum, map.getOrDefault(sum,0) + 1);
}
}
// Count the sum of the remaining two elements,
// find out whether the sum is 0 in the map, and record the number of occurrences
for(int i : nums3){
for(int j : nums4){
res += map.getOrDefault(0 - i - j, 0);
}
}
return res;
}
}
题目链接：383. 赎金信
状态：一次性Accepted。思路来源于前一篇文章的编号为242的题目，思路基本一样。
看到题目时第一想法：用一个长度为26的数组来记录magazine里字母出现的次数。然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
依然是数组在哈希法中的应用。完整代码如下： 时间复杂度O(N)，空间复杂度O(1)
class Solution { //Java
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()){
return false;
}
// define a hashmap array
int[] record = new int[26];
// iterate
for(char c: magazine.toCharArray()){
record[c - 'a'] += 1;
}
for(char c: ransomNote.toCharArray()){
record[c - 'a'] -= 1;
}
// if there is negative numbers in the array, it means that there are
// characters in the ransomNote string that are not in the magazine
for(int i : record){
if(i < 0){
return false;
}
}
return true;
}
}
题目链接：15. 三数之和
状态：之前学过此题，但是再做依然犯错，可见其细节之多。
看到题目时第一想法：三数之和倒是不难，双指针外嵌套一个for循环，但是去重是个麻烦事。
具体解析看这里
我只列举其中重点信息：
- 双指针找结果的思路：先对数组排序，然后遍历数组，双指针left在遍历数组的下一位，right从数组最后一位，然后sum等于三数之和。如果sum大了，就把right左移；如果sum小了，就把left右移。
- 遍历数去重：与nums[i]比较时，我们应选择与nums[i-1]比较。否则就会出现{-1,-1,2}这种结果被错误筛选掉的情况。
- left和right的去重：一定要先保存一个可行的结果！去重的时候就是判断left与右边一位是否相等，若相等，就跳过。right与其左边一位是否相等，若相等，就跳过。
完整代码如下：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
// Find a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.length; i++) {
// If the first element is greater than zero after sorting,
// then no combination can sum to zero, so return the result immediately
if (nums[i] > 0) {
return result;
}
// Skip duplicate elements for 'a'
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--; // If the sum is greater than zero, move the 'right' pointer left
} else if (sum < 0) {
left++; // If the sum is less than zero, move the 'left' pointer right
} else {
// If the sum is zero, add the triplet to the result
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicate elements for 'b' and 'c'
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// Move both pointers to find the next potential triplet
right--;
left++;
}
}
}
return result;
}
}
题目链接：18. 四数之和
状态：看似与三数之和类似，实际上是细节里也有些许区别。最终是照着代码才做出来。
看到题目时第一想法：在三数之和的基础上又增加一层for循环。但是后来才发现题目要求变了，target可以是负数的情况下一开始的剪枝判断就会发生一些改变。
完整解析看这里
我只在三数之和的基础上列举一些需要注意的地方：
- 之所以说不能在一开始就用if(nums[i] > target){return;}是因为会出现数组为{-4,-1,0,0}，而target正好等于-5这种解被误剪掉。原因就是target可以为负数的情况下，是可以通过负数的叠加 越加越小的。
- 时间复杂度的分析：对于15.三数之和 双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。
以下是完整代码：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // Sort the array to simplify the process of finding quadruplets
for (int i = 0; i < nums.length; i++) {
// Pruning: If the current number is greater than zero and also greater than the target,
// then no valid quadruplet can be found, so return the result immediately
if (nums[i] > 0 && nums[i] > target) {
return result;
}
// Skip duplicate elements for the first number
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
// Skip duplicate elements for the second number
if (j > i + 1 && nums[j - 1] == nums[j]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (right > left) {
// Use long to prevent integer overflow when summing four integers
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--; // If the sum is greater than the target, move the 'right' pointer left
} else if (sum < target) {
left++; // If the sum is less than the target, move the 'left' pointer right
} else {
// If the sum is equal to the target, add the quadruplet to the result
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// Skip duplicate elements for the third and fourth numbers
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++; // Move both pointers to find the next potential quadruplet
right--;
}
}
}
}
return result;
}
}
