1.两数之和

image.png

解法1：暴力解法【线性查找】

  1. //空间复杂度O(1) 空间复杂度O(n^2)
  2. class Solution {
  3.     public int[] twoSum(int[] nums, int target) {
  4.         if(nums==null||nums.length==0){return new int[0];}
  5.         for(int i=0;i<nums.length;i++){
  6.             int x=nums[i];
  7.             for(int j=i+1;j<nums.length;j++){
  8.                 if(nums[j]==target-x){
  9.                     return new int[]{i,j};
  10.                 }
  11.             }
  12.         }
  13.         return new int[0];
  14.     }
  15. }

解法2：二分查找

由于该题目要求给出值的索引，二分查找的前提是数组有序的，这样就打乱了原来数组的索引，如果硬要这么做，需要开辟额外的空间来记住原有的值的索引，所以在这里不适合用二分查找！

解法3：哈希查找优化

  1. // 时间复杂度O(n) 空间复杂度O(n) -->开辟了一个map,最大是数组长度
  2. class Solution {
  3.     public int[] twoSum(int[] nums, int target) {
  4.         if(nums==null||nums.length==0){return new int[0];}
  5.         HashMap<Integer,Integer> map=new HashMap<>();
  7.         for(int i=0;i<nums.length;i++){  //O(n)
  8.             map.put(nums[i],i);
  9.         }
  11.         for(int i=0;i<nums.length;i++){  //O(n)
  12.             int x=nums[i];
  13.             if(map.containsKey(target-x)){
  14.                 int index=map.get(target-x);
  15.                 //防止使用同一元素两次
  16.                 if(i!=index){
  17.                      return new int[]{i,index};
  18.                 }
  19.             }
  20.         }
  21.         return new int[0];
  22.     }
  23. }

再次优化

  1. // 时间复杂度：O(n)
  2. // 空间复杂度：O(n)
  3. public int[] twoSum(int[] nums, int target) {
  4.     if (nums == null || nums.length == 0) return new int[0];
  5.     int n = nums.length;
  7.     Map<Integer, Integer> map = new HashMap<>();
  8.     // O(n)
  9.     for (int i = 0; i < n; i++) { 
  10.         int x = nums[i];
  11.         // 哈希查找
  12.         if (map.containsKey(target - x)) {
  13.             int index = map.get(target - x);
  14.             return new int[]{i, index};
  15.         }
  16.         map.put(x, i); //核心思想：有可能在数组的前几个元素就有答案了，后面的元素就没必要加                            进map
  17.     }
  18.     return new int[0];
  19. }

2.两数之和 II - 输入有序数组

image.png

这道题可以用暴力解法，也可以用hash解法，但是hash解法有一个缺点，需要开辟额外一个map配合使用。
这道题给的数组是有序的，那么我们可以使用二分查找，快且不需要开辟空间。

解法1：二分查找

  1. //时间复杂度O(nlogn)
  2. class Solution {
  3.     public int[] twoSum(int[] nums, int target) {
  4.         if (nums == null || nums.length == 0) return new int[0];
  6.         for(int i=0;i<nums.length;i++){
  7.             int x=nums[i];
  8.             //在i+1~nums.length-1区间二分查找
  9.             int index=binarySerach(nums,i+1,nums.length-1,target-x);
  10.             if(index!=-1){
  11.                 return new int[]{i+1,index+1};
  12.             }
  13.         }
  14.         return new int[0];
  15.     }
  16.     private int binarySerach(int[] nums,int left,int right,int target){
  17.         while(left<=right){
  18.             //防止数值溢出int_Max
  19.             int mid=left+(right-left)/2;
  20.             if(nums[mid]==target)
  21.                 return mid;
  22.             else if(nums[mid]>target)
  23.                 right=mid-1;
  24.             else
  25.                 left=mid+1;
  26.         }
  27.         return -1;
  28.     }
  29. }

解法2：双指针

因为该数组有序，所以可以在两边设置指针，让最小的指针和最大的指针相加，如果还是小于target，那么最小指针往右移动，大于同理。就可以实现时间复杂度低于二分查找，空间复杂度不变的优化。

  1. // 时间复杂度：O(n)
  2. // 空间复杂度：O(1)
  3. class Solution {
  4.     public int[] twoSum(int[] nums, int target) {
  5.         if (nums == null || nums.length == 0) return new int[0];
  7.         int left=0;
  8.         int right=nums.length-1;
  10.         while(left<=right){
  11.             if(nums[left]+nums[right]==target)
  12.                 return new int[]{left+1,right+1};
  13.             else if(nums[left]+nums[right]<target)
  14.                 left++;
  15.             else
  16.                 right--;
  17.         }
  18.         return new int[0];
  19.     }    
  20. }

两数之和 IV - 输入 BST

image.png
BST二叉查找树中根结点大于左子节点，小于右子节点。刚好中序遍历二叉查找树生成一条有序的数组，可以根据这条数组进行双指针解决。

方案1：双指针

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. //时间复杂度O(n)
  17. class Solution {
  18.     public boolean findTarget(TreeNode root, int k) {
  19.         if(root==null) return false;
  20.         List<Integer> nums=new ArrayList<>();
  21.         inOrder(root,nums);
  23.         int left=0;
  24.         int right=nums.size()-1;
  25.         while(left<right){
  26.             int sum=nums.get(left)+nums.get(right);
  27.             if(sum==k) 
  28.                 return true;
  29.             else if(sum>k)
  30.                 right--;
  31.             else
  32.                 left++;
  33.         }
  34.         return false;
  35.     }
  36.      //中序遍历 左中右
  37.     private void inOrder(TreeNode node,List<Integer> nums){
  38.         if(node==null) return;
  40.         inOrder(node.left,nums);
  41.         nums.add(node.val);
  42.         inOrder(node.right,nums);
  43.     }
  44. }

解法2：哈希查找

将每一次遍历的结点，与set集合中的元素进行比较，如果该结点+集合中元素==target，那么直接返回true，不用再进行遍历。

  1. class Solution {
  2.     public boolean findTarget(TreeNode root, int k) {
  3.         if(root==null) return false;
  4.         return find(root,k,new HashSet<>());
  5.     }
  6.     private boolean find(TreeNode node, int target, Set<Integer> set) {
  7.         //前序遍历 中左右
  8.         if(node==null) return false;
  9.         if(set.contains(target-node.val)) return true;
  10.         set.add(node.val);
  11.         //一直遍历左结点 直到左节点为null才开始遍历右节点
  12.         return find(node.left,target,set)||find(node.right,target,set);
  13.     }
  14. }

补充：
image.png
DLR—前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
LDR—中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
LRD—后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

三数之和

解法1：暴力解法

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         if(nums==null||nums.length<3)
  4.             return new ArrayList<>();
  6.         //使用hashSet避免集合重复
  7.         Set<List<Integer>> set=new HashSet<>();
  8.         //因为需要集合中的元素不重复，所以进行排序
  9.         Arrays.sort(nums);  //O(nlogn)
  11.         //O(n^3)
  12.         for(int i=0;i<nums.length;i++){
  13.             for(int j=i+1;j<nums.length;j++){
  14.                 for(int k=j+1;k<nums.length;k++){
  15.                     if(nums[i] + nums[j] + nums[k] == 0){
  16.                          set.add(Arrays.asList(nums[i],nums[j],nums[k]));
  17.                     }
  18.                 }
  19.             }
  20.         }
  21.         return new ArrayList<>(set);
  22.     }
  23. }

解法2：双指针

固定一个元素，然后设置两个指针指向剩余的元素，将该两个指针指向的元素相加，如果等于固定的元素的符数，那就是其中一个答案。由于是有序的，所以这两个指针可以配合二分查找。

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         if(nums==null||nums.length<3)
  4.             return new ArrayList<>();
  6.         //使用hashSet避免集合重复
  7.         Set<List<Integer>> set=new HashSet<>();
  8.         //因为需要集合中的元素不重复，所以进行排序
  9.         Arrays.sort(nums);  //O(nlogn)
  11.         //O(n^2)
  12.         for(int i=0;i<nums.length;i++){
  13.             int target=-nums[i];
  14.             int left=i+1;
  15.             int right=nums.length-1;
  17.            while(left<right){
  18.            int sum=nums[left]+nums[right];   
  19.             if(sum==target){            
  20.                 set.add(Arrays.asList(nums[i],nums[left],nums[right]));
  21.                 left++;
  22.                 right--;
  23.             }else if(sum <target){
  24.                 left++;
  25.             }else{
  26.                 right--;
  27.             }
  28.         }
  29.       }
  30.         return new ArrayList<>(set); //O(n)
  31.     }
  32. }

对Set转List进行优化

使用HashSet的目的是为了去重，那么如果不利用HashSet的去重特性，该怎么去重？

  1. left和right指针的下一个/前一个元素跟当前指向的元素值相同，则跳过下一个/前一个元素，指向下下个元素或前前个元素

  2. 固定元素i的下一个元素如果同当前元素值相同，那么下一次循环的结果肯定是相同的，所以应该跳过下一个元素。

    1. class Solution {
    2.  public List<List<Integer>> threeSum(int[] nums) {
    3.      if(nums==null||nums.length<3)
    4.          return new ArrayList<>();
    6.      List<List<Integer>> list=new ArrayList<>();
    7.      Arrays.sort(nums);
    9.      for(int i=0;i<nums.length;i++){
    10.          //当前元素跟上一个元素相同则跳过，i+1和i比较的话，就会导致还没拿到答案就跳过了
    11.          if(i>0&&nums[i]==nums[i-1]) continue;
    12.          int target=-nums[i];
    13.          int left=i+1;
    14.          int right=nums.length-1;
    15.         while(left<right){
    16.           int sum=nums[left]+nums[right];   
    17.          if(sum==target){            
    18.              list.add(Arrays.asList(nums[i],nums[left],nums[right]));
    19.              //++left：先让left往后移 然后才拿到left+1后的值再进行判断 而不是先拿left进行判断再往后移
    20.              while(left<right&&nums[left]==nums[++left]);
    21.              while(left<right&&nums[right]==nums[--right]);                
    22.          }else if(sum <target){
    23.              left++;
    24.          }else{
    25.              right--;
    26.          }
    27.      }
    28.      }
    29.      return list;
    30.  }
    31. }

四数之和

image.png

  1. class Solution {
  2.     public List<List<Integer>> fourSum(int[] nums, int target) {
  3.         if (nums == null || nums.length < 4)
  4.         return new ArrayList<>();
  6.         Arrays.sort(nums);
  7.         List<List<Integer>> res = new ArrayList<>();
  9.         for(int i=0;i<nums.length;i++){
  10.             if(i>0&&nums[i]==nums[i-1]) continue;
  12.             for(int j=i+1;j<nums.length;j++){
  13.                 if(j>i+1&&nums[j]==nums[j-1]) continue;
  15.                 int partSum=nums[i]+nums[j];
  16.                 int left=j+1;
  17.                 int right=nums.length-1;
  19.                 while(left<right){
  20.                     int sum=partSum +nums[left]+nums[right];
  21.                     if(sum==target){
  22.                         res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
  23.                         while(left<right&&nums[left]==nums[++left]);
  24.                         while(left<right&&nums[right]==nums[--right]);
  25.                     }else if(sum<target)
  26.                         left++;
  27.                     else
  28.                         right--;
  29.                 }
  30.             }
  31.         }
  32.         return res;
  34.     }
  35. }

解法同三数之和一样，区别只不过是固定两个数

两数之和 II - 输入有序数组