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;
    }
}

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

发表评论