文章目录

15.三数之和(中等)暴力法：会超时官解：排序+双指针法官解：排序+双指针法 稍微优化一点使用hashmap去重(过程中)使用hashmap去重(结束) (过了99.37%) 18.四数之和(中等)安安：暴力法(通过了)排序+双指针 二维数组(List< List< Integer>>)去重 leetcode每日一题汇总

15.三数之和(中等)

暴力法：会超时

/* 思路： 用了最简单的暴力法，但是直接暴力结果中会出现重复 所以在暴力遍历的时候，要去除会产生重复的情况 */ //anan 2020.10.05 class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int i = 0; i < n; i++){ if(i > 0 && nums[i] == nums[i-1]) continue; for(int j = i+1; j < n; j++){ if(j != (i+1) && nums[j] == nums[j-1]) continue; for(int k = j+1; k < n; k++){ if(k != (j+1) && nums[k] == nums[k-1]) continue; if(nums[i]+nums[j]+nums[k] == 0){ res.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[k]))); } } } } return res; } }

官解：排序+双指针法

//anan 2020.10.05 class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int k = 0; k < n-2; k++){ if(nums[k] > 0) break; if(k > 0 && nums[k] == nums[k-1]) continue; //去重 int left = k+1; int right = n-1; while(left < right){ if(nums[k]+nums[left]+nums[right] < 0){ while(left < right && nums[left+1] == nums[left]) left++; //去重 left++; }else if(nums[k]+nums[left]+nums[right] > 0){ while(left < right && nums[right-1] == nums[right]) right--; //去重 right--; }else{ res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[left], nums[right]))); while(left < right && nums[left+1] == nums[left]) left++; //去重 while(left < right && nums[right-1] == nums[right]) right--; //去重 left++; right--; } } } return res; } }

官解：排序+双指针法 稍微优化一点

//anan 2020.10.05 class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int k = 0; k < n-2; k++){ if(nums[k] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环 if(k > 0 && nums[k] == nums[k-1]) continue; //去重 int left = k+1; int right = n-1; while(left < right){ if(nums[k]+nums[left]+nums[right] < 0){ //这个不放到最终结果里，所以不去重也没关系 //while(left < right && nums[left+1] == nums[left]) left++; //去重 left++; }else if(nums[k]+nums[left]+nums[right] > 0){ //while(left < right && nums[right-1] == nums[right]) right--; //去重 right--; }else{ res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[left], nums[right]))); while(left < right && nums[left+1] == nums[left]) left++; //去重 while(left < right && nums[right-1] == nums[right]) right--; //去重 left++; right--; } } } return res; } }

使用hashmap去重(过程中)

//anan 2020.10.05 class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Map<List<Integer>, Integer> map = new HashMap<>(); int n = nums.length; Arrays.sort(nums); for(int k = 0; k < n-2; k++){ if(nums[k] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环 int left = k+1; int right = n-1; while(left < right){ if(nums[k]+nums[left]+nums[right] < 0){ left++; }else if(nums[k]+nums[left]+nums[right] > 0){ right--; }else{ //如果之前有的话，就不加入了 if(!map.containsKey(Arrays.asList(nums[k], nums[left], nums[right]))){ res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[left], nums[right]))); map.put(Arrays.asList(nums[k], nums[left], nums[right]), 1); } left++; right--; } } } return res; } }

使用hashmap去重(结束) (过了99.37%)

通不过案例：[0,0,0,0,0,…]

//anan 2020.10.05 class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int k = 0; k < n-2; k++){ if(nums[k] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环 int left = k+1; int right = n-1; while(left < right){ if(nums[k]+nums[left]+nums[right] < 0){ left++; }else if(nums[k]+nums[left]+nums[right] > 0){ right--; }else{ res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[left], nums[right]))); left++; right--; } } } System.out.println("res:"+res); Map<List<Integer>, Integer> map = new HashMap<>(); for(int i = 0; i < res.size();){ if(map.containsKey(res.get(i))){ System.out.println("重复："+ res.get(i)); res.remove(i); }else{ map.put(res.get(i), 1); i++; } } return res; } }

18.四数之和(中等)

安安：暴力法(通过了)

/* 输入 [-2,-1,-1,1,1,2,2] 0 输出 [[-2,-1,1,2],[-1,-1,1,1]] */ /* 思路： 用了最简单的暴力法，但是直接暴力结果中会出现重复 所以在暴力遍历的时候，要去除会产生重复的情况 */ //anan 2020.10.05 class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int i = 0; i < n; i++){ if(i > 0 && nums[i] == nums[i-1]) continue; for(int j = i+1; j < n; j++){ if(j != (i+1) && nums[j] == nums[j-1]) continue; for(int k = j+1; k < n; k++){ if(k != (j+1) && nums[k] == nums[k-1]) continue; for(int t = k+1; t < n; t++){ if(t != (k+1) && nums[t] == nums[t-1]) continue; if(nums[i]+nums[j]+nums[k]+nums[t] == target){ res.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[k],nums[t]))); } } } } } return res; } }

排序+双指针

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int i = 0; i < n-3; i++){ if(i > 0 && nums[i] == nums[i-1]) continue; //去重 for(int j = i+1; j < n-2; j++){ if(j > i+1 && nums[j] == nums[j-1]) continue; //去重 int left = j+1; int right = n-1; while(left < right){ if(nums[i]+nums[j]+nums[left]+nums[right] < target){ left++; }else if(nums[i]+nums[j]+nums[left]+nums[right] > target){ right--; }else{ res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]))); while(left < right && nums[left+1] == nums[left]) left++; //去重 while(left < right && nums[right-1] == nums[right]) right--; //去重 left++; right--; } } } } return res; } }

二维数组(List< List< Integer>>)去重

import java.util.*; /* 输入： [[-4, -2, 6], [-4, -2, 6], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2], [-2, -2, 4], [-2, -2, 4], [-2, 0, 2], [-2, -2, 4], [-2, 0, 2], [-2, 0, 2]] */ public class Main { public static void main(String[] args) { List<List<Integer>> res = new ArrayList<>(); res.add(Arrays.asList(-4,-2,6)); res.add(Arrays.asList(-4,-2,6)); res.add(Arrays.asList(-4,0,4)); res.add(Arrays.asList(-4,1,3)); res.add(Arrays.asList(-4,2,2)); res.add(Arrays.asList(-2,-2,4)); res.add(Arrays.asList(-2,-2,4)); res.add(Arrays.asList(-2,0,2)); res.add(Arrays.asList(-2,-2,4)); res.add(Arrays.asList(-2,0,2)); res.add(Arrays.asList(-2,0,2)); System.out.println("去重前：res:"+res); Map<List<Integer>, Integer> map = new HashMap<>(); for(int i = 0; i < res.size();){ if(map.containsKey(res.get(i))){ System.out.println("重复："+ res.get(i)); res.remove(i); }else{ map.put(res.get(i), 1); i++; } } System.out.println("去重后：res:"+res); } } /* 去重前：res:[[-4, -2, 6], [-4, -2, 6], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2], [-2, -2, 4], [-2, -2, 4], [-2, 0, 2], [-2, -2, 4], [-2, 0, 2], [-2, 0, 2]] 重复：[-4, -2, 6] 重复：[-2, -2, 4] 重复：[-2, -2, 4] 重复：[-2, 0, 2] 重复：[-2, 0, 2] 去重后：res:[[-4, -2, 6], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2], [-2, -2, 4], [-2, 0, 2]] */