LeetCode454 四数相加
给定四个包含整数的数组列表 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
解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
思路：
找出存在的结果，存在性问题，想到使用哈希表去解决。本题找四个值加起来等于0。解法类似于两数之和那一题，
那一题是判断两数之和等于指定值，判断目标值减一个数是否存在。本题也可以这么做。四个数，我们可以拆成两个一组
这样可以保证时间复杂度平分，变成n^2,如果是三个一组和一个一组进行比较，时间复杂度取得是n^3。我们这题是求出现的次数
所以还需要一个值来存次数，想到可以使用map，key存两数之和进行目标值比对，value存出现次数用来统计。
代码：
package com.dwj.LeetCode.HashList; import java.util.HashMap; import java.util.Map; /** * 四数相加 * 判断四数相加等于0出现的次数 */ public class FourNumberPlus { class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> map = new HashMap<>(); int temp; int res = 0; //统计两个数组中的元素之和，同时统计出现的次数，放入map for (int i : nums1) { for (int j : nums2) { temp = i + j; if (map.containsKey(temp)) { map.put(temp, map.get(temp) + 1); } else { map.put(temp, 1); } } } //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数 for (int i : nums3) { for (int j : nums4) { temp = i + j; if (map.containsKey(0 - temp)) { res += map.get(0 - temp); } } } return res; } } }
LeetCode 15 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
思路：
本题的难点在于去重。三个元素更改顺序不算新的。使用双指针写法。首先需要对数组进行一个排序操作。方便使用双指针法移动
规定一个起始位置，起始位后后的最左最右规定left和right。判断三数之和的时候，起始位置不动，left和right由于是数组其他元素的
最大最小值，可以根据计算结果的偏差，调整left和right，最终寻找到一个合适的值。
本题的重点在于去重操作
a的去重（起始不变的那个元素）：
也就是不变的当前起始位置，需要与上一个循环的起始位置值比较是否相同，如果相同，没有移动的意义，需要把起始位置继续后移。num[i] == num[i-1]，continue跳过。 这样做防止取重复的固定位置的值。
为什么不用num[i] == num[i+1]?因为如果是【-1，-1，2，3，4】。我在取到第一个-1就去判断第二个位置的-1，这样做的话，就把[-1,-1,2]的这种可能排除掉了，如果取后一位进行比较，会影响到b的取值，不可取。
所以要和前一位比较最合理。
b和c的去重：
left和right的值，不能与移动路径的下一位相同，这个很好理解。如果right和left的下一个移动路径上的值相同，那么这次移动获取到的值是没有意义的。
代码：
package com.dwj.LeetCode.HashList; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 判断三数之和等于0的集合。 */ public class ThreeNumberPlus { class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { return result; } if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.length - 1; while (right > left) { int sum = nums[i] + nums[left] + nums[right]; if (sum > 0) { right--; } else if (sum < 0) { left++; } else { result.add(Arrays.asList(nums[i], nums[left], nums[right])); while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; right--; left++; } } } return result; } } }
原文地址：http://www.cnblogs.com/dwj-ngu/p/16802273.html
