454. 四数相加 II
// 这道题使用哈希就可解决，使用一个map存储前两个数组中，所有组合产生的sum的频率；对于后两个数组中所有的组合，每出现一个和的相反数出现在map中，则代表出现了这个相反数频率个组合可以满足四数相加为0
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map12 = new HashMap<>();
for(int n1 : nums1){
for(int n2: nums2){
map12.put(n1+n2, map12.getOrDefault(n1+n2, 0) + 1);
}
}
int ans = 0;
for(int n1 : nums3){
for(int n2: nums4){
ans += map12.getOrDefault(-(n1+n2), 0);
}
}
return ans;
}
}
15. 三数之和
总体思路看了题解后会写了，但左右指针那里绕了我很久，一直想不明白为什么可以保证不漏掉解。刚刚才理解。这个要从第一轮迭代开始算起，此时left = i + 1, right = nums.length - 1, 对于他们而言，没有左侧或右侧的选择。此时若sum > 0，则必然可以保证right对应的数字一定不存在与任何解（以num[i]为第一个数字）中。对于sum < 0也是相同的，所以若是指针移动，则一定可以保证，不包含这个数字的解或者已经被存储了。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length - 2; i++){
if(nums[i] > 0) return ans;
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1;
int right = nums.length - 1;
while(left < right){
if(nums[i] + nums[left] + nums[right] == 0) {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
while(left < right && nums[left]==nums[left+1]) left++;
while(left < right && nums[right]==nums[right-1]) right--;
left++; right--;
}else if(nums[i] + nums[left] + nums[right] > 0) right--;
else left++;
}
}
return ans;
}
}
18. 四数之和
三数之和会了做这个就会简单许多，就是增加了一层循环。需要注意的时，题目给了nums[i]的取值范围，$-109<nums[i]<109$，因此，四个数字之和可能越界，需要使用long来存储结果。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
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, right = nums.length - 1;
while(left < right){
long sum = (long)nums[left] + nums[right] + nums[i] + nums[j]; //使用long避免越界
if(sum == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while(left < right && nums[left] == nums[left+1]) left++;
while(left < right && nums[right] == nums[right-1]) right--;
left++; right--;
}else if(sum > target) right--;
else left++;
}
}
}
return ans;
}
}