LeetCode 454. 四数相加Ⅱ
题目链接：四数相加Ⅱ题目链接
思路
这道题目给定我们四个数组，让我们判断从四个数组中分别取一个元素，然后将这四个元素相加，值为 0 的元组个数，所以我们可以模仿两数之和，因为四个数组中分别取元素就是任意取，不需要考虑去重的问题，所以可以将四个数组转换成两个数组。然后使用两数之和的方法来做。
代码
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res=0;
//key存储的是两个数组元素的和，value存的是和出现的次数
Map<Integer,Integer>map=new HashMap<Integer,Integer>();
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)
{
res+=map.getOrDefault(0-i-j,0);
}
return res;
}
}
LeetCode 383. 赎金信
题目链接：赎金信题目链接
思路
这道题目给定了两个字符串数组，一个数组是杂志数组，一个数组是赎金信数组。我们需要保证可以从杂志数组中获取所有赎金信数组中的字符，所以我们设置一个数组 record 用来记录，如果杂志数组中有相应的单词，则 record++, 如果赎金信数组中有相应的单词，则 record–。最终，如果 record 数组中的值全部大于 0，则说明可以从杂志数组中获取所有赎金信数组中的字符，否则则不能。
代码
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length()>magazine.length())
return false;
int[] record=new int[26];
for(char c:magazine.toCharArray())
{
record[c-'a']++;
}
for(char c:ransomNote.toCharArray())
{
record[c-'a']--;
}
for(int i=0;i<26;i++)
{
if(record[i]<0)
return false;
}
return true;
}
}
LeetCode15.三数之和
题目链接：三数之和题目链接
思路
这道题目要求我们在一个数组中获取三个元素，它们的和为 0，并且三个元素组成的元组结果值是不能重复的。这道题目主要的关键点是去重，我们使用双指针的做法，首先使用 i 遍历这个数组元素，i 执行去重操作就是使用 nums[i]==nums[i-1] 进行判断，因为我们后续的 left 指针为 left=i+1, 所以我们是无法使用 nums[i]==nums[i+1] 来进行判断的。然后设置 left 指针为 left=i+1，设置 right 指针为 right=nums.length-1, 然后判断三个指针指向的元素和是否为 0，因为我们之前首先要对数组进行排序操作，所以如果和大于 0，则我们将 right 值减 1，如果和小于 0，我们将 left 值加 1，后续又要考虑 left 和 right 值的去重操作，left 值的去重操作是使用 nums[left]==nums[left+1]，right 值的去重操作是使用 nums[right]==nums[right-1]。因为结果不能重复，所以判断出一个值后，需要 left 和 right 分别指向加减操作。
代码
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)
{
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;
}
}
LeetCode 9. 四数之和
题目链接：四数之和题目链接
思路
跟三数之和的思路是相同的，区别在于去重和剪枝的变化。
代码
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(nums[k]>target&&nums[k]>=0)
return result;
if(k>0&&nums[k]==nums[k-1])
continue;
for(int i=k+1;i<nums.length;i++)
{
if(nums[k]+nums[i]>target&&nums[k]+nums[i]>=0)
break;
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++;
left++;
right--;
}
}
}
}
return result;
}
}