欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leetcode之哈希法与双指针法求多数之和

程序员文章站 2022-05-03 23:43:13
目录1. leetcode 1. 两数之和2. leetcode 15. 三数之和3. leetcode 18. 四数之和4. leetcode 454. 四数相加 II1. leetcode 1. 两数之和leetcode 1. 两数之和(难度:简单)题目要求:给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。示例...

1. leetcode 1. 两数之和

leetcode 1. 两数之和(难度:简单)
题目要求:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]

public class 两数之和 {
    /**
     * 哈希法
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        // Map的key存放的是数组元素值,value存放的是对应的下标
        // 注意:相同的key会被覆盖,但是这种解法即使后面的元素覆盖了前面的,也不会影响结果
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        // 重新遍历一遍数组,判断Map中是否存在 target - nums[i] 的值,由于数组中同一个元素不能使用两遍,因此这个值对应的数组下标不能跟i相等
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i]) && i != map.get(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
        }
        return new int[2];
    }
}
2. leetcode 15. 三数之和

leetcode 15. 三数之和(难度:中等)
题目要求:
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = []
输出:[]
示例 3:
输入:nums = [0]
输出:[]
提示:
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

public class 三数之和 {
    /**
     * 双指针解法
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) {
            return res;
        }
        // 对数组进行排序
        Arrays.sort(nums);
        // 遍历一遍数组,初始时:左指针left指向当前遍历到的元素的下一位,右指针right指向数组的最后一位,三数之和即为nums[i]+nums[left]+nums[right]
        for (int i = 0; i < nums.length - 2; i++) {
            // 如果当前遍历到的元素值大于0,直接结束循环
            if (nums[i] > 0) {
                return res;
            }
            // 第一次去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < 0) {
                    // 左指针收缩,让整体值变大
                    left++;
                } else if (nums[i] + nums[left] + nums[right] > 0) {
                    // 右指针收缩,让整体值变小
                    right--;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    // 左右指针同时收缩
                    left++;
                    right--;
                    // 第二次去重
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}
3. leetcode 18. 四数之和

leetcode 18. 四数之和(难度:中等)
题目要求:
给定一个包含 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]
]

public class 四数之和 {
    /**
     * 双指针法
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 4) {
            return res;
        }
        // 对数组进行排序
        Arrays.sort(nums);
        // 双重循环遍历一遍数组,初始时:左指针left指向第二层循环当前遍历到的元素的下一位,右指针right指向数组的最后一位,四数之和即为nums[i]+nums[j]+nums[left]+nums[right]
        for (int i = 0; i < nums.length - 3; i++) {
            // 第一次去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                // 第二次去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 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 {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        res.add(list);
                        // 左右指针同时收缩
                        left++;
                        right--;
                        // 第三次去重
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }
            }
        }
        return res;
    }
}

4. leetcode 454. 四数相加 II

leetcode 454. 四数相加 II (难度:中等)
题目要求:
给定四个包含整数的数组列表 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 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果不会超过 2^31 - 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

public class 四数相加II {
    /**
     * 哈希法
     * 思路:将两个数组看成一组进行处理,首先创建一个Map集合,key存放AB数组中各元素的和,value存放相同和的个数
     *      然后分别遍历CD数组,并查看Map集合中是否存在值等于 0-(C+D) 的key,存在则结果值加上对应的value
     * @param A
     * @param B
     * @param C
     * @param D
     * @return
     */
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> map = new HashMap<>();
        // 先分别遍历AB数组,填充map集合
        for (int a : A) {
            for (int b : B) {
                if (map.containsKey(a + b)) {
                    map.put(a + b, map.get(a + b) + 1);
                } else {
                    map.put(a + b, 1);
                }
            }
        }
        int sum = 0;
        // 分别遍历CD数组
        for (int c : C) {
            for (int d : D) {
                if (map.containsKey(0 - c - d)) {
                    sum += map.get(0 - c - d);
                }
            }
        }
        return sum;
    }
}

本文地址:https://blog.csdn.net/can_chen/article/details/113973451