leetcode两数、三数、四数之和

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

两数之和

题目

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

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

方法二：HashMap空间换时间

借助HashMap实现，如下图示例

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;

四数之和

方法原理和上面一样，借助HashMap和三重for循环实现

ps:计划每日更新一篇博客，今日2023-04-22，日更第六天，昨日更新：LeetCode6_N字形变换