NC61：两数之和

1.NC61：两数之和:

给出一个整数数组，请在数组中找出两个加起来等于目标值的数，你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2
注意：下标是从1开始的,假设给出的数组中只存在唯一解

给出的数组为 {2, 7, 11, 15},目标值为9
输出 ndex1=1, index2=2

解法1：暴力求解：

第一层遍历每个数，在遍历每个数的同时，遍历其他的数是不是他的补(target-self, complement)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int i=0;i<numbers.length;i++){
            for(int j=i+1;j<numbers.length;j++){
                if(numbers[i]+numbers[j]==target){
                    return new int[]{i+1,j+1};
                }
            }
        }
        return null;
    }
}

解法2：哈希表

时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。

1. 首先我们定义一个哈希表map后，我们就将number[i]进行标记,即map[number[i]]=i
2. 然后我们使用一层for循环查询map里面有没有target-number[i]
3. 如果有就返回map[target- number[i]] + 1和i + 1
4. 如果没有就查询下一个

   import java.util.HashMap;
   public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<numbers.length;i++){
            if(map.containsKey(target-numbers[i])){
                return new int[]{map.get(target-numbers[i])+1,i+1};
            }
            else{
                map.put(numbers[i],i);
            }
        }
        return null;
    }
   }

2.三数之和：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路：标签：数组遍历

• 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集

• 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环

• 如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过

• 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++

• 当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−

• 时间复杂度：O(n2)，n 为数组长度

  import java.util.*;
  public class Solution {
     public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
         ArrayList<ArrayList<Integer>> res=new ArrayList<>();
  
         if(num==null || num.length<3){
             return res;
         }
         Arrays.sort(num);// 排序
         for(int i=0;i<num.length-2;i++){
             if(num[i]>0){
                 break;// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
             }
             if(i>0 && num[i]==num[i-1]){
                 continue;// 去重
             }
             int L=i+1;
             int R=num.length-1;
  
             while(L<R){
                 int sum=num[i]+num[L]+num[R];
                 if(sum==0){
     //res.add(new ArrayList<>(Arrays.asList(num[i],num[L],num[R])))
                     ArrayList<Integer> list=new ArrayList<>();
                     list.add(num[i]);
                     list.add(num[L]);
                     list.add(num[R]);
                     res.add(list);
  
                     while(L<R && num[L]==num[L+1]){
                         L++;// 去重
                     }
                     while(L<R && num[R]==num[R-1]){
                         R--;// 去重
                     }
                     L++;
                     R--;
                 }
                 else if(sum>0){
                     R--;
                 }
                 else if(sum<0){
                     L++;
                 }
             }
         }
         return res;
     }
  }

3.四数之和：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c+ d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

与3sum思路类似，只不过这次需要先固定两个数，然后双指针找，用set去除重复组合

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>>res = new ArrayList<>();
        if(num==null||num.length<4)return res;
        Arrays.sort(num);
        for(int i=0;i<num.length-3;i++){
            if(num[i]+num[i+1]+num[i+2]+num[i+3]>target)break;
            if(num[i]+num[num.length-3]+num[num.length-2]+num[num.length-1]<target)continue;
            for(int j=i+1;j<num.length-2;j++){
                int k = j+1;
                int l = num.length-1;
                while(k<l){
                    if(num[i]+num[j]+num[k]+num[l]==target){
                        ArrayList<Integer>tmp = new ArrayList<>();
                        tmp.add(num[i]);
                        tmp.add(num[j]);
                        tmp.add(num[k]);
                        tmp.add(num[l]);
                        k++;
                        l--;
                        if(!res.contains(tmp))
                            res.add(tmp);
                    }else if(num[i]+num[j]+num[k]+num[l]>target){
                        l--;
                    }else 
                        k++;
                }
            }
        }
        return res;
    }
}