454.四数相加II
这个第一时间的想法: 在合并前两组和后两组的集合后进行排序，结果超时了，其实没必要排序的。
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
List<Integer> list1 = new ArrayList<>();
Map<Integer,Integer> map = new HashMap<>();
for (int i:nums1){
for (int j:nums2){
Integer val = i+j;
Integer old = map.getOrDefault(val, 0);
map.put(val,old+1);
}
}
int count = 0;
for (int i : nums3) {
for (int j : nums4) {
Integer val = -(i+j);
count += map.getOrDefault(val,0);
}
}
return count;
}
- 赎金信
这个太简单了
public boolean canConstruct(String ransomNote, String magazine) {
int[] store = new int[26];
for (int i=0;i<magazine.length();i++){
store[magazine.charAt(i)-'a']++;
}
for (int i=0;i<ransomNote.length();i++){
int val = ransomNote.charAt(i) - 'a';
if (store[val] == 0) return false;
store[val]--;
}
return true;
}
- 三数之和
这个之前做过，第一时间想法是对的,先排序。
public List<List<Integer>> threeSum(int[] nums) {
int len = nums.length;
if(len <3){
return new ArrayList();
}
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList();
for(int i=0;i<len;i++){
int left = i+1,right = len-1;
if(nums[i]>0){
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while(left<right && nums[right]>=0){
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;
}
- 四数之和
这个与上一题相似
public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums.length < 4) return new ArrayList<>();
Arrays.sort(nums);
int len= nums.length;
List<List<Integer>> result = new ArrayList<>();
for (int i=0;i<len-3;i++){
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
//如果最小值大于target就可以结束整个循环
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
//如果当次循环的最大值比target小就下个循环
if ((long) nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {
continue;
}
for (int j=i+1;j<nums.length-2;j++){
int left = j+1;
int right = len-1;
if (j > i+1 && nums[j] == nums[j - 1]) {
continue;
}
long front = nums[i] + nums[j];
//如果最小值大于target就可以结束整个循环
if (front + nums[left] + nums[left+1] > target) {
break;
}
//如果当次循环的最大值比target小就下个循环
if (front + nums[right - 1] + nums[right] < target) {
continue;
}
long res = target - front;
while (left<right){
long t = nums[left] + nums[right];
if (t > res){
right--;
}else if (t < res){
left++;
}else {
result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
//去重
while (left<right && nums[left] == nums[left+1]){
left++;
}
left++;
while (left<right && nums[right] == nums[right-1]){
right--;
}
right--;
}
}
}
}
return result;
}
