leetcode两数、三数、四数之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode两数、三数、四数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

如有错误，感谢不吝赐教、交流

两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

方法一：暴力两重循环（不可取）

方法二：HashMap空间换时间

借助HashMap实现，如下图示例
leetcode两数、三数、四数之和

public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(target - nums[0], 0);
        int res [] = new int[2];
        for (int i = 1; i < nums.length; i++) {
            Integer index = map.get(nums[i]);
            if (index != null) {
                res[0] = (int) index;
                res[1] = i;
                break;
            } else {
                map.put(target - nums[i], i);
            }
        }
        return res;
    }

三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。 这里尤其注意一下，不能包含重复的三元组（借助HashSet实现比较简单，不过有点费时间和空间）

方法一：当然是暴力破解啦

直接使用三重for循环暴力破解，太费时间，不可取。

方法二：同两数之和的原理，借助HashMap和HashSet实现

要求是三个数之和，这里将其中一个数保存到HashMap中，再使用双重for循环遍历，即可获得三个数的答案
原理是和两数之和的原理一样。
这里需要注意，会出现重复的组合结果，如[0, 0,0,0]，可能得组合就有[0,0,0], [0,0,0], [0,0,0]
显然这里重复了，于是使用HashSet去重。

// 先对nums排序
        Arrays.sort(nums);
        HashMap<Integer, Integer> map = new HashMap<>();
        HashSet<List<Integer>> hashSet = new HashSet<>();
        map.put(-nums[0], 1);
        for (int i = 1; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int i1 = nums[i] + nums[j];
                Integer map_val = map.get(i1);
                if (map_val != null) {
                    List<Integer> integers = new ArrayList<>();
                    integers.add(-i1);
                    integers.add(nums[i]);
                    integers.add(nums[j]);
                    hashSet.add(integers);
                }
            }
            map.put(-nums[i], 1);
        }
        List<List<Integer>> lists = new ArrayList<>(hashSet);
        return lists;