1）两数和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0; i<nums.length; i++){
if(map.get(target-nums[i])!=null){
return new int[]{map.get(target-nums[i]).intValue(),i};
}else{
map.put(nums[i],i);
}
}
return new int[]{-1,-1};
}
}
2）三数和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Arrays.sort(nums);
if(nums.length<3) return result;
for(int i=0; i<nums.length; i++){
if(nums[i]>0)break;
if(i>0 && nums[i]==nums[i-1]){//remove the duplicates
continue;
};
int L=i+1;
int R=nums.length-1;
int sum;
while(L<R){
sum = nums[i]+nums[L]+nums[R];
if(sum<0){
L++;
}else if(sum>0){
R--;
}else{
result.add(Arrays.asList(nums[i],nums[L],nums[R]));
//remove the duplicate
while(L<R && nums[L+1]==nums[L])L++;
while(L<R && nums[R]==nums[R-1]) R--;
L++;
R--;
}
}
}
return result;
}
}
public List<List<Integer>> threeSum(int[] nums) {
//1. check input
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length<3) return result;
//2. Sort the array so we can remove the duplicates later easily.
Arrays.sort(nums);
for(int i=0; i<nums.length-2 && nums[i]<=0; i++){
int l=i+1, r = nums.length-1;
while(l<r){
if(nums[i] + nums[l] + nums[r] == 0){
result.add( new ArrayList<Integer>(Arrays.asList(nums[i],nums[l],nums[r])));
while(l+1<r && nums[l+1] == nums[l]) l++;
while(r-1>l && nums[r-1] == nums[r]) r--;
l++;
r--;
}else if(nums[i] + nums[l] + nums[r] < 0){
l++;
}else{
r--;
}
}
while(i+1<nums.length && nums[i+1]==nums[i])i++;
}
return result;
}
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] ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums==null || nums.length<4) return result;
Arrays.sort(nums);
int sum;
for(int i=0; i< nums.length-3;i++){
if(i>0 && nums[i]==nums[i-1])continue;
int newTarget = target - nums[i];
//get other 3 which sum is newTarget
for(int j=i+1; j<nums.length;j++){
if(j>i+1 && nums[j-1]==nums[j])continue;
int L=j+1;
int R=nums.length-1;
while(L<R){
sum = nums[j]+nums[L]+nums[R];
if(sum==newTarget){
result.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
while(L<R && nums[L+1]==nums[L])L++; //remove the duplicate values from the beginning.
while(L<R && nums[R-1]==nums[R])R--; //remove the duplicate values from the end.
//continue to find others
L++;
R--;
}else if(sum<newTarget){
L++;
}else{
R--;
}
}
}
}
return result;
}
}
4）四数和（2）
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。 例如: 输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出: 2 解释: 两个元组如下: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
int N = A.length;
if(N==0) return 0;
int count=0;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0; i<N; i++){
for(int j=0;j<N; j++){
int sum1 = A[i]+B[j];
//record how many times for this sum1
map.put(sum1, map.getOrDefault(sum1, 0)+1);
}
}
for(int m=0; m<N; m++){
for(int n=0;n<N; n++){
int sum2 = C[m]+D[n];
count += map.getOrDefault(0-sum2,0);
}
}
return count;
}
}
5）和为K的子数组
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 说明 : 数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subarray-sum-equals-k 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
6）和可被 K 整除的子数组
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。 示例： 输入：A = [4,5,0,-2,-3,1], K = 5 输出：7 解释： 有 7 个子数组满足其元素之和可被 K = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3] 提示： 1 <= A.length <= 30000 -10000 <= A[i] <= 10000 2 <= K <= 10000 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一
class Solution {
public int subarraysDivByK(int[] A, int K) {
int count =0;
int len = A.length;
int[] B = new int[len+1];
int[] modValArr = new int[K];
int modVal;
//sum the first i and store it into B[i];
for(int i=0; i<len;i++){
B[i+1]=B[i]+A[i];
modVal = (B[i+1]%K+K)%K;
modValArr[modVal] = modValArr[modVal] + 1;
}
/*能被整除的则modVal为0，应该为n*(n+1)/2; */
count += ((modValArr[0] +1 ) * modValArr[0])/2;
/*不能被整除的则应该为（n－1）*(n－1 + 1)/2; */
for(int j=0; j<K; j++){
count += ((modValArr[j]-1) * modValArr[j])/2;
}
return count;
}
}
7）两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 说明: 返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一
class Solution {
public int[] twoSum(int[] numbers, int target) {
/*HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0; i<numbers.length; i++){
int complmenet = target-numbers[i];
if(complmenet<numbers[0])break;
if(map.containsKey(complmenet)){
return new int[]{map.get(complmenet)+1,i+1};
}else{
map.put(numbers[i],i);
}
}
return new int[]{};*/
int l=0;
int h=numbers.length-1;
int sum;
while(l<h){
sum= numbers[l]+numbers[h];
if(sum==target){
return new int[]{l+1,h+1};
}else if(sum<target){
l++;
}else{
h--;
}
}
return new int[]{-1,-1};
}
}
8）两数之和 IV - 输入 BST
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
案例 2:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
输出: False
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一：
class Solution {
ArrayList list = new ArrayList();
public boolean findTarget(TreeNode root, int k) {
boolean found = false;
inOrder(root);
int l=0;
int h=list.size()-1;
while(l<h){
int sum = (Integer)list.get(l) + (Integer)list.get(h);
if(sum==k){
return true;
}else if(sum<k){
l++;
}else{
h--;
}
}
return false;
}
public void inOrder(TreeNode root){
if(root==null)return;
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
}
9) 查找两棵二叉搜索树之和
给出两棵二叉搜索树，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值 Target。 如果可以找到返回 True，否则返回 False。
https://blog.csdn.net/qq_17550379/article/details/102289763
最后送上一个leetcode的github链接： https://github.com/luliyucoordinate/Leetcode