一.简介
这篇介绍一类问题，求解数组中是否多个数相加的和，都可以利用 Hash + 指针的方式查找。
二.示例
2.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]
提示
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案。
实现 1
public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); int length = nums.length; for (int i = 0; i < length; i++) { //两数相加，根据一个数值查找是否已经存在 if(map.containsKey(target - nums[i])){ return new int[]{map.get(target - nums[i]),i}; } map.put(nums[i],i); } return new int[0];}
复制代码
实现 2-暴力枚举
class Solution { public int[] twoSum(int[] nums, int target) { int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { //i + j 的值是否等于查询值 if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[0]; }}
复制代码
2.2 三数之和
给你一个包含 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
-105 <= nums[i] <= 105
实现 1
public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; //因为有重复的组合，所有先排序，为了好剔除重复 Arrays.sort(nums); List<List<Integer>> list = new ArrayList<>(); for (int first = 0; first < n; first++) { //去除重复值 if(first > 0 && nums[first] == nums[first - 1]){ continue; } //a + b + c == target //b+c = target - a // 根据这个等式推出 a <= b <= c int target = 0; target -= nums[first]; // c 的索引值 int third = n - 1; for (int second = first+1; second < n; second++) { //b重复值 if(second > (first+1) && nums[second] == nums[second -1]){ continue; } //第二索引必须小于第三索引 ，b + c 如果大于 target ，那么可以推测出第三个值大了，c的third 索引值减少 while(second < third && nums[second] + nums[third] > target){ --third; } //第三个和第二个索引值相等 if(second == third){ break; } //第二 + 第三 等于 target if(target == nums[second] + nums[third]){ List<Integer> childs = new ArrayList<>(); childs.add(nums[first]); childs.add(nums[second]); childs.add(nums[third]); list.add(childs); } } } return list; }
复制代码
2.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]
]
实现 1
根据 2.2 三数之和，可以推测出类似的做法，运用遍历+ 指针的方式，a+b+c+d == target ，边界条件 a <= b <= c <= d 。
public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> quadruplets = new ArrayList<List<Integer>>(); //边界判断，必须得满足4个值，才可以得出结果 if (nums == null || nums.length < 4) { return quadruplets; } //排序，处理重复组合 Arrays.sort(nums); int length = nums.length; //第一个值，所以边界length - 3 for (int i = 0; i < length - 3; i++) { //处理a第一个，重复判断 if (i > 0 && nums[i] == nums[i - 1]) { continue; } //a+b+c+d 大于target 直接退出，数组有顺序。 if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) { break; } //第一个加上，尾部后面三个值都小于target ，推测第一个值不够大 if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) { continue; } //第二个值处理 for (int j = i + 1; j < length - 2; j++) { //处理重复值判断 if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } //a+b+c+d 大于target 直接退出，数组有顺序。 if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) { break; } //第一个加上第二，尾部后面三个值都小于target ，推测第二个值不够大 if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) { continue; } //第三个值 ，第四个值 int left = j + 1, right = length - 1; while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); //处理第三值重复 while (left < right && nums[left] == nums[left + 1]) { left++; } left++; //处理第四个值重复 while (left < right && nums[right] == nums[right - 1]) { right--; } right--; } else if (sum < target) { //第三值小了 left++; } else { //第四个值大了 right--; } } } } return quadruplets; }
复制代码
参考
https://leetcode-cn.com/problems/two-sum/description/
https://leetcode-cn.com/problems/3sum/description/
https://leetcode-cn.com/problems/4sum/
公众号
微信号：bigdata_limeng
评论