# 查找表
- 查找有无
- 元素 a 是否存在？—— Set
- 查找对应关系（键值对应）
- 元素 a 出现了几次？—— Map
- 明确我们要查找的是什么？key 是什么？value 是什么？
# Java 中的 Set
Set：元素无序、不可重复的集合
- HashSet：HashTable 实现，无序
- TreeSet：红黑树实现
- LinkedHashSet：HashTable 实现数据存储，双向链表记录顺序。
# 添加、删除、修改操作
add(Object obj): 添加一个元素
addAll(Collection coll): 添加整个集合
void clear(): 清空集合
boolean remove(Object obj): 删除一个元素
boolean removeAll(Collection coll): 删除一个集合中存在的元素
# 元素查询的操作
boolean contains(Object obj): 判断是否存在元素 obj
boolean containsAll(Collection c): 判断是否存在集合 c 中的所有元素
boolean isEmpty(): 判断集合是否为空
int size(): 获得集合中元素的个数
# Java 中的 Map
Map 接口：双列数据，保存具有映射关系“key-value”的集合。
- HashMap：JDK7 数组+链表存储数据，JDK 8 数组+链表+红黑树存储数据，线程不安全，
- ConcurrentHashMap：JDK7 是基于分段锁实现线程安全，JDK8 是 CAS + synchronized 实现线程安全。
- HashTable：线程安全
- TreeMap：基于红黑树实现。
- LinkedHashMap：基于 HashTable 数据结构，使用链表保存插入顺序
# 添加、删除、修改操作
Object put(Object key,Object value)：将指定 key-value 添加到(或修改)当前 map 对象中
void putAll(Map m)：将 m 中的所有 key-value 对存放到当前 map 中
Object remove(Object key)：移除指定 key 的 key-value 对，并返回 value
void clear()：清空当前 map 中的所有数据
# 元素查询的操作
Object get(Object key)：获取指定 key 对应的 value
boolean containsKey(Object key)：是否包含指定的 key
boolean containsValue(Object value)：否包含指定的 value
int size()：返回 map 中 key-value 对的个数
boolean isEmpty()：判断当前 map 是否为空
boolean equals(Object obj)：判断当前 map 和参数对象 obj 是否相等
# 元视图操作的方法
Set keySet()：返回所有 key 构成的 Set 集合
Collection values()：返回所有 value 构成的 Collection 集合
Set entrySet()：返回所有 key-value 对构成的 Set 集合
# Set 的使用
Set 的三大核心特点决定了它的作用：
- 集合：判断存在性
- 无序
- 不可重复：去重
# Leetcode 349 Intersection of Two Arrays
https://leetcode-cn.com/problems/intersection-of-two-arrays/
因为题目要求：
- 求交集；
- 输出结果中的元素不可重复；
所以天然可以考虑使用 Set 来自动去重，思路如下：
- 先把 nums1 的元素都扔进 Set set 中；
- 遍历 nums2，并逐个判断元素是否存在于 Set set 中；
- 如果存在，那就是交集，将该元素扔进另外一个 Set result 中；
- 最后将 Set result 转为 int[] 返回即可；
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1 == null || nums2 == null) {
return null;
}
// Set：自动去重，也方便后面再转为数组
Set<Integer> result = new HashSet<>();
// Set: 利用不可重复性来去重
Set<Integer> set = new HashSet<>();
// 先把 nums1 的元素都扔进 set，Set 会自动去重
for(int i=0; i<nums1.length; i++){
set.add(nums1[i]);
}
// 再判断 set 中是否存在 nums2 的元素，存在的话，就是交集，同时利用 Set 来去重
for(int i=0; i<nums2.length; i++){
if(set.contains(nums2[i])) {
result.add(nums2[i]);
}
}
// result 就是答案了，转为数组即可
Object[] temp = result.toArray();
int[] res = new int[temp.length];
for(int i=0; i<res.length; i++){
res[i] = (Integer)temp[i];
}
return res;
}
}
# Leetcode 202 Happy Number
https://leetcode-cn.com/problems/happy-number/
此题的关键就是要避免陷入死循环，也就是在变换过程中，两次得到了两个一样的数，那它就会一直陷入死循环，永远不会变为 1。所以我们需要记录出每次变换后得到的值，如果重复了，就直接返回 false 即可，如果没有重复，就继续变换，直到找到答案。对于不重复，我们可以采用 Set 这个集合。
class Solution {
public boolean isHappy(int n) {
if (n == 1) {
return true;
}
// 用 Set 来记录每次变换后的值；
Set<Integer> set = new HashSet<>();
set.add(n);
// 变换
while(true) {
n = convertor(n);
// 等于 1，符合「快乐数」的定义
if (n == 1){
return true;
}
// 重复，则陷入死循环，false
if (set.contains(n)) {
return false;
}
set.add(n);
}
}
// 该数替换为它每个位置上的数字的平方和
public int convertor(int n){
int result = 0;
int left = 0;
while(n != 0){
left = n % 10;
n = n / 10;
result += left * left;
}
return result;
}
}
# Map 的使用
Map 的三大特性决定了它的作用：
- 集合：判断存在性
- 键值对：存储对应关系
- Key 不可重复：计数
# Leetcode 350 Intersection of Two Arrays II
https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
本题跟 349 的区别是输出的结果中的元素是可以重复的，如果一个元素出现了多次，就以 nums1 和 nums2 中出现较少的那个为主。所以我们需要记录元素出现的个数。这个时候就可以使用 Map 了。思路如下：
- 先将 nums1 中的元素扔进一个 Map<Integer, Integer> 中，Key 表示值，Value 表示该值出现的次数；
- 然后遍历 nums2，如果存在于 Map 且 Value 大于 0 的话，就放进一个 List 中；
- 得到的 List 遍是结果了；
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if(nums1 == null || nums2 == null) {
return null;
}
List<Integer> result = new LinkedList<>();
// 利用 Map 来计数
// Key 表示值
// Value 表示该值出现的次数
Map<Integer, Integer> map = new HashMap<>();
// 将 nums1 中的元素扔进 Map 并计数
for (int i=0; i<nums1.length; i++){
Integer ele = map.get(nums1[i]);
if(ele == null) {
map.put(nums1[i], 1);
} else {
map.put(nums1[i], ele + 1);
}
}
// 遍历 nums2，判断是否存在于 Map，且 Value 值大于 0
for (int i=0; i<nums2.length; i++){
Integer ele = map.get(nums2[i]);
if(ele != null && ele > 0){
result.add(nums2[i]);
map.put(nums2[i], ele - 1);
}
}
// result 就是答案了，转为数组即可
int[] res = new int[result.size()];
for(int i=0; i<res.length; i++){
res[i] = result.get(i);
}
return res;
}
}
# Leetcode 242 Valid Anagram
https://leetcode-cn.com/problems/valid-anagram/
s 和 t 每个字符出现的次数都相同，很明显是需要计数的，我们可以用 Map 来解决此问题。思路如下：
- 比较 s 和 t 的长度，必须相等，不等则 false；
- 遍历 s，将 s 的每个字符都扔进 Map<Character, Integer> 中，Key 表示字符值，Value 表示其出现的个数；
- 遍历 t，判断 t 中的字符是否都存在 Map 中：
- 如果不存在，则直接返回 false；
- 如果存在，则判断 Value 是否大于 0 ：
- 大于 0：则 Value--；
- 不大于 0：则返回 false；
- 遍历完 t 后，由于 s 和 t 的长度相等，其实已经不需要再进行额外验证了，说明答案是 true。
class Solution {
public boolean isAnagram(String s, String t) {
// 长度不等，直接 false
if(s.length() != t.length()) {
return false;
}
Map<Character, Integer> map = new HashMap<>();
// 遍历 s，将 s 的每个字符都放入 Map<Character, Integer> 中；
// Key: 字符值;
// Value: 字符出现的次数
for(int i=0; i<s.length(); i++){
Integer count = map.get(s.charAt(i));
if(count == null || count == 0){
map.put(s.charAt(i), 1);
} else {
map.put(s.charAt(i), count + 1);
}
}
// 遍历 t，判断 t 中的每个字符是否都存在 Map 中且 Value 要一直满足大于 0
// 遍历完如果还没意外的话，由于 s 和 t 相等，则说明二者互为字母异位词
// 无需额外检验
for (int i=0; i<t.length(); i++){
Integer count = map.get(t.charAt(i));
if(count == null || count <= 0){
return false;
} else {
map.put(t.charAt(i), count - 1);
}
}
return true;
}
}
PS: 此方法并不是最优解，此处只是为了展示 Map 的作用。
# Leetcode 290 Word Pattern
https://leetcode-cn.com/problems/word-pattern/
此题要求 pattern 和 word 是一一对应的，正反都要对应。这种对应关系很明显可以用 Map 来解决。又因为正反都要一一对应，所以其实我们是可以用两个 Map 来解决的：
- Map<Character, String>
- Map<String, Character>
略显复杂。下面给出一种思路，只需要一个 Map 即可解决问题：
- 开一个 Map<Character, String>，Key 表示 pattern，Value 表示 word；
- map.get(pattern.charAt(i)) == words[i] 满足，则 pattern -> word 满足；
- 如果 map.get(pattern.charAt(i)) 不存在，但是 map.containsValue(sChildren[i]) 存在，则表示 word -> pattern 不满足；
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] sChildren = s.split(" ");
if(pattern == null || pattern.length() != sChildren.length){
return false;
}
// Key: pattern
// Value: word
HashMap<Character, String> map = new HashMap<>();
for(int i=0;i<pattern.length();i++){
if(map.containsKey(pattern.charAt(i))){
// 判断 pattern -> word 是不是一一对应
String str = map.get(pattern.charAt(i));
if(!str.equals(sChildren[i])){
return false;
}
}else{
// 判断 word -> pattern 是不是一一对应
if(map.containsValue(sChildren[i])){
return false;
}else{
map.put(pattern.charAt(i),sChildren[i]);
}
}
}
return true;
}
}
# Leetcode 205 Isomorphic Strings
https://leetcode-cn.com/problems/isomorphic-strings/
思路同 Leetcode 290。
class Solution {
public boolean isIsomorphic(String s, String t) {
if ( (s == null || s.length() == 0) && (t == null || t.length() == 0) ) {
return true;
}
if ( (s == null || s.length() == 0) || (t == null || t.length() == 0) ) {
return false;
}
if (s.length() != t.length()) {
return false;
}
// Key: s 中的某个字符；
// Value: s 中的某个字符对应到 t 中的某个字符
// s -> t, t -> s 都要一一对应
Map<Character, Character> map = new HashMap<>();
for(int i=0; i<s.length(); i++){
Character c = map.get(s.charAt(i));
if (c != null) {
// 判断 s -> t 是否一一对应
if (!c.equals(t.charAt(i))) {
return false;
}
} else {
// 判断 t -> s 是否一一对应
if(map.containsValue(t.charAt(i))) {
return false;
}
map.put(s.charAt(i), t.charAt(i));
}
}
return true;
}
}
# Leetcode 451 Sort Characters By Frequency
https://leetcode.cn/problems/sort-characters-by-frequency/
本题需要我们记录字符出现的频率，很明显得用 HashMap<字符，频率>，另外又要对字符出现的频率进行排序，我们可以实现一个 sort，也可以直接调用内置的 sort 方法。笔者这里提供另外一个思路，HashMap 用来记录 HashMap<字符, 字符 *n>，然后使用一个优先级队列 PriorityQueue 来记录 HashMap 的 values，并重写其 Comparator，将长度长的，排在队头，最后再依次取出 Queue 中的元素，组成 String 即可。
总结：HashMap<字符, 字符 * n> + PriorityQueue<String>：
- 创建一个优先级队列 PriorityQueue<String>，并重写比较器，让 s.length() 大的排队头；
- 创建一个 HashMap<Character, String>；
- 遍历 s 中的每一个字符：
- 如果不存在于 HashMap，就插入 [char, char]；
- 如果存在于 HashMap，就 [char, map[char] + char]
- 将 map.values() 依次放入 PriorityQueue 中，让它自动排序；
- 依次从 PriorityQueue 中取出元素，拼接成 String，即可。
class Solution {
public String frequencySort(String s) {
PriorityQueue<String> queue = new PriorityQueue<>((a,b) -> b.length() - a.length());
HashMap<Character, String> m = new HashMap<>();
// 遍历 s 中的每一个字符：
// 如果不存在于 HashMap，就插入 [char, char]；
// 如果存在于 HashMap，就 [char, map[char] + char]
for (int i = 0; i < s.length(); i++) {
if (!m.containsKey(s.charAt(i))) {
m.put(s.charAt(i), s.charAt(i) + "" );
} else {
m.put(s.charAt(i), m.get(s.charAt(i)) + s.charAt(i));
}
}
// 将 map.values() 依次放入 PriorityQueue 中，让它自动排序；
for (String value: m.values()) {
queue.add(value);
}
StringBuilder sb = new StringBuilder();
//依次从 PriorityQueue 中取出元素，拼接成 String，即可。
while (queue.size() != 0) {
sb.append(queue.poll());
}
return sb.toString();
}
}
# 灵活选择键值
# Leetcode 454 Four Sum II
https://leetcode-cn.com/problems/4sum-ii/
暴力算法时间复杂度是 O(n4)，虽然 N<=200，但复杂度还是过于大了。O(n3) 也不小。我们要尽可能控制在 O(n2)。基本思路：
- 将 C + D 的每一种可能放入查找表，key 为 C[k] + D[l]，value 为该和出现的次数；
- 再穷尽 A 和 B，这样时间复杂度就是 O(n2)；
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
m := make(map[int]int, 40000)
// 1. 将 C + D 的每一种可能放入查找表，key 为 C[k] + D[l]，value 为该和出现的次数；
for k:=0; k< len(nums3); k++ {
for l := 0; l < len(nums4); l ++ {
if v, ok := m[nums3[k] + nums4[l]]; ok {
m[nums3[k] + nums4[l]] = v + 1
} else {
m[nums3[k] + nums4[l]] = 1
}
}
}
res := 0
// 2. 穷尽 A + B，寻找 A[i] + B[j] == - m[C[k] + D[j]]
for i := 0; i < len(nums1); i++ {
for j := 0; j < len(nums2); j++ {
if v, ok := m[-nums1[i] - nums2[j]]; ok {
res += v
}
}
}
return res
}
# Leetcode 49 Group Anagrams
https://leetcode-cn.com/problems/group-anagrams/
字母异位词 意味着只要我们对字符串进行排序，那么它们都会变成一样的，所以我们可以利用一个 Map，key 存储排序后的字符串，value 存储排序前的索引集合。这样 Map 就存储我们要的结果了。整体思路：
- 创建一个 Map，key 存储排序后的字符串，value 存储排序前的索引集合；
- 遍历 strs，对每个 str 进行排序 str`，判断 str` 是否在 Map 中：
- 在，就在 value 中追加索引 append(v, index)；
- 不在，就在 value 新建 []int{index}；
func groupAnagrams(strs []string) [][]string {
var res [][]string
m := make(map[string][]int, 0)
for index, str := range strs {
l := []byte(str)
// 1. 排序
sort.Slice(l, func(i, j int) bool {
return l[i] < l[j]
})
// 2. 记录
// key 用来记录排序后的单词，字母异位词排序后应该是相同的
// value 用来记录字母异位词的索引
if v, ok := m[string(l)]; ok {
m[string(l)] = append(v, index)
} else {
m[string(l)] = []int{index}
}
}
for _, v := range m {
var tmp []string
for _, i := range v {
tmp = append(tmp, strs[i])
}
res = append(res, tmp)
}
return res
}
# Leetcode 447 Number of Boomerangs
https://leetcode-cn.com/problems/number-of-boomerangs/
首先我们来确定几个问题：
找什么？
找回旋镖，欧式距离（p1, p2） = 欧式距离（p1, p3）
需不需要去重？
不需要，起点不一样，顺序不一样，都认为是不同的回旋镖
key 是什么？
value 是什么？
解决了 1 和 2 问题，我们就可以有以下思路了：
- 依次遍历 points；
- 分别以 points[i] 为起点寻找回旋镖；
- 建立一个 map，key 存储其他点到 point[i] 的欧式距离，value 则存储该距离的点的个数；
- 因为相同距离的点可以两两组合，可以顺序不一样就不算重复，所以个数为 n(n-1) ；
- 这样我们就可以遍历 value 来计算回旋镖的数量了；
func numberOfBoomerangs(points [][]int) int {
res := 0
// 1. 分别以 point[i] 为起点寻找回旋镖
for i:=0; i<len(points); i++ {
// 2. 建立 map 来记录回旋镖
// key: 到 point[i] 的距离
// value: 相同距离的点的个数
m := make(map[int]int, 0)
for j:=0; j<len(points);j ++ {
if i == j {
continue
}
// 3. 记录到 point[i] 相同距离的点的个数
m[oDistance(points[i], points[j])] = m[oDistance(points[i], points[j])] + 1
}
// 4. 统计以 point[i] 为起点的回旋镖的个数
for _, count := range m {
res += count * (count - 1)
}
}
return res
}
func oDistance(i []int, j []int) int {
return (i[0] - j[0]) * (i[0] - j[0]) + (i[1] - j[1]) * (i[1] - j[1])
}
# Leetcode 149 Max Points on a Line
https://leetcode-cn.com/problems/max-points-on-a-line/
思路同 Leetcode 447 Number of Boomerangs，我们用一个 map 来记录斜率的数据：
- key：以点 points[i] 为枢纽，points[j] 与 points[i] 的斜率；
- value：相同斜率的点的个数；
基本思路如下：
- 依次遍历 points；
- 以每个 points[i] 为枢纽，建立一个 m，记录其他点与 points[i] 的斜率及其个数；
- 不断保留斜率相同个数最多的数；
- 注意要考虑斜率为无穷大的表示方式，这里用了 verticalCount 和 vertical 变量来辅助记录。
func maxPoints(points [][]int) int {
res := 0
for i:=0; i<len(points); i++ {
// key: point[i] 与 point[j] 斜率
// value: 以 point[i] 为枢纽，相同斜率的点的个数
m := make(map[float64]int, 0)
verticalCount := 0 // 斜率无穷大的个数
for j:=0; j<len(points); j++ {
if j == i {
continue
}
// 计算斜率
if gd, vertical := gradient(points[i], points[j]); !vertical {
verticalCount ++
} else {
m[gd] = m[gd] + 1
}
}
// 寻找斜率相同最多的
if res < verticalCount + 1 { // + 1是因为 point[i] 也得算进去，下面同理
res = verticalCount + 1
}
for _, v := range m {
if res < v + 1{
res = v + 1
}
}
}
return res
}
// 斜率无穷大就返回 false 来表示
func gradient(point1 []int, point2 []int) (float64, bool) {
if point1[0] == point2[0] {
return 0.0, false
}
return float64((point2[1] - point1[1])) / float64((point2[0] - point1[0])), true
}
# 结合滑动窗口
# Leetcode 219 Contains Duplicate II
https://leetcode.cn/problems/contains-duplicate-ii/
- 建立一个 map，用来存储元素是否存在，key 为值，value 则 0 表示不存在，1 表示存在；
- 建立大小为 k 的窗口（元素个数为 k+1）；
- 先将 [0, k] 中的元素放入 map 并判断是否有重复，如有，则直接 return true；
- 左出右进滑动窗口，直到遍历完 nums；
func containsNearbyDuplicate(nums []int, k int) bool {
if k <= 0 {
return false
}
m := make(map[int]int, k)
// 先存入第一个窗口
for i:=0; i<len(nums) && i <= k; i++ {
if m[nums[i]] != 0 {
return true
} else {
m[nums[i]] = 1
}
}
// 窗口不小于 nums 长度，还找不到，那就不用滑动了
if len(nums) <= k + 1 {
return false
}
// 滑动大小窗口，左出右入，继续尝试寻找重复元素
for i:=k; i + 1<len(nums);i++ {
// 左出
m[nums[i-k]] = 0
// 右进
if m[nums[i+1]] != 0 {
return true
} else {
m[nums[i+1]] = 1
}
}
return false
}
# Leetcode 220 Contains Duplicate III
https://leetcode.cn/problems/contains-duplicate-iii/
参考 Leetcode 219 Contains Duplicate II，本题我们也可以使用滑动窗口来解决本题，不过窗口中要寻找的条件就变了：
- 寻找 v -t <= nums[i] <= v + t
这里我们可以借助 Java 中的 TreeSet，它的 key 是有序的，并且提供了两个方法：
ceiling(entry)：返回大于等于 entry 中最小的 key；floor(entry)：返回小于等于 entry 中最大的 key；
于是我们的条件就是：
- 寻找 m.ceilingKey((long)nums[i] - t) 的 nums[j]，且它要满足 <= nums[i] + t
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
//为了防止溢出，需要用 long 类型
TreeSet<Long> treeSet = new TreeSet<>();
//遍历数组
for(int i=0;i<nums.length;i++){
// 判断是否存在元素 x >= nums[i]-t
Long number = treeSet.ceiling((long)nums[i]-(long)t);
// 如果存在，还需要这个元素 x <= nums[i]+t
if(number != null && number <= (long)nums[i]+(long)t){
return true;
}else{
// 不存在就继续往 TreeSet 中扔元素
treeSet.add((long)nums[i]);
// 检查是否越出窗口
if(treeSet.size() > k){
treeSet.remove((long)nums[i-k]);
}
}
}
return false;
}
}
# 经典问题
# Leetcode 1 Two Sum
https://leetcode-cn.com/problems/two-sum/
因为 nums 无序，所以不能采取对撞指针的方式。本题可以巧借 Map，思路如下：
- 开一个 Map 来存储数组中数值请求，达到 O(1) 的查找效率。Key 表示值，Value 表示其在 nums 中的索引；
- 判断 [0...i) 中有没有 target - nums[i]
- 有就返回 {i, map.get(target-nums[i])}
- 没有就把 <nums[i], i> 扔进 map 中，继续往后走
class Solution {
public int[] twoSum(int[] nums, int target) {
// 开一个 Map 来存储数组中数值请求，达到 O(1) 的查找效率
// Key: 值
// Value: 其在 nums 的索引
Map<Integer, Integer> map = new HashMap<>();
// 判断 [0...i) 中有没有 target - nums[i]
// 有就返回 {i, map.get(target-nums[i])}
// 没有就把 <nums[i], i> 扔进 map 中，继续往后走
for(int i=0; i<nums.length; i++){
int search = target - nums[i];
if(map.containsKey(search)) {
return new int[]{i, map.get(search)};
} else {
map.put(nums[i], i);
}
}
return new int[]{-1, -1};
}
}
# Leetcode 15 Three Sum
https://leetcode-cn.com/problems/3sum/
有了 TwoSum 的经验之后，我们的思路就是把 ThreeSum 转为多个 TwoSum。本体要求记录所有不重复的三元组，也就是得去重，这里比较好的思路就是先将 nums 排序，这样去重比较方便。整体思路：
- 先将 nums 排序；
- 建立三个索引， k，i，j，这样就转为寻找 nums[i] + nums[j] = - nums[k] 的 TwoSum 之和，再由于 nums 是有序的，所以可以用双指针夹逼；
- 每次确定了 k，就在 [k + 1, len(nums)-1] 中寻找 nums[i] + nums[j] = - nums[k] ；
- 去重 ①，即对 k 去重。当寻找完 target 为 - nums[k] 之后，如果 nums[k+1] == nums[k]，那就不需要再寻找 nums[k+1] 了，因为必定是重复的，所以直接 k++，直到没有重复的；
- 去重 ②，即对 i，j 去重，当找到 nums[i] + nums[j] = - nums[k] 之后，要继续寻找符合条件的 i 和 j，因为 nums 有序，所以我们需要 i++ 和 j-- 到 nums[i] 与 nums[j] 都跟之前不重复为止，这样才避免重复。
func threeSum(nums []int) [][]int {
// 1. 排序
sort.Ints(nums)
var res [][]int
// 2. 寻找 nums[i] + nums[j] = - nums[k]
for k:=0; k < len(nums) - 2; k ++ {
// ① 对 k 去重
if k > 0 && nums[k] == nums[k-1] {
continue
}
// 3. 转为 TwoSum：寻找 nums[i] + nums[j] = - nums[k]
if tmp := twoSum(nums, k + 1, len(nums) - 1, - nums[k]); len(tmp) > 0 {
res = append(res, tmp...)
}
}
return res
}
func twoSum(nums []int, start, end, target int) [][]int {
var res [][]int
// 双指针夹逼
for ; start < end; {
if nums[start] + nums[end] == target {
res = append(res, []int{nums[start], nums[end], -target})
// ② 对 i 和 j 去重
start ++
for ; start < end && nums[start] == nums[start - 1]; start++ {
}
end --
for ; start < end && nums[end] == nums[end + 1]; end-- {
}
} else if nums[start] + nums[end] < target {
start ++
} else {
end --
}
}
return res
}
# Leetcode 18 Four Sum
https://leetcode-cn.com/problems/4sum/
思路同 TwoSum 升级为 ThreeSum 一样，我们要把 FourSum 转为多个 ThreeSum。
func fourSum(nums []int, target int) [][]int {
var res [][]int
// 1. 排序
sort.Ints(nums)
// 2. 转为三元问题
for k:=0 ; k < len(nums) - 3; k ++ {
// ① 对 k 去重
if k > 0 && nums[k] == nums[k-1] {
continue
}
if tmp := threeSum(nums, k+1, len(nums) -1, target - nums[k]);
len(tmp) > 0 {
for _, v := range tmp {
v = append(v, nums[k])
res = append(res, v)
}
}
}
return res
}
func threeSum(nums []int, start, end, target int) [][]int {
var res [][]int
// 3. 转为二元问题
for k:=start; k <= end - 2; k ++ {
// ① 对 k 去重
if k > start && nums[k] == nums[k-1] {
continue
}
// 寻找 nums[i] + nums[j] = - nums[k]
if tmp := twoSum(nums, k + 1, len(nums) - 1, target - nums[k]);
len(tmp) > 0 {
for _, v := range tmp {
v = append(v, nums[k])
res = append(res, v)
}
}
}
return res
}
func twoSum(nums []int, start, end, target int) [][]int {
var res [][]int
// 双指针夹逼
for ; start < end; {
if nums[start] + nums[end] == target {
res = append(res, []int{nums[start], nums[end]})
// ② 对 i 和 j 去重
start ++
for ; start < end && nums[start] == nums[start - 1]; start++ {
}
end --
for ; start < end && nums[end] == nums[end + 1]; end-- {
}
} else if nums[start] + nums[end] < target {
start ++
} else {
end --
}
}
return res
}
# Leetcode 16 Three Sum Closest
https://leetcode-cn.com/problems/3sum-closest/
结合前面的 TwoSum 升级为 ThreeSum，我们本题的思路还是要想办法将 ThreeSumClosest 降级为 TwoSumClosest。不难证明以下规律（其中 >> 表示最接近的意思）：
- 如果 a + b + c >> target，且 a 是固定的，那么 b + c >> target - a
所以本体就有了以下思路：
- 先排序，方便去重，减少计算量；
- 建立索引 k，它负责确定 a + b + c 中的 a；
- 然后再 nums[k+1, len(nums)-1] 中，寻找 b + c >> target - a；
- 最终确定最靠近 target 的 a + b + c
func threeSumClosest(nums []int, target int) int {
// 1. 排序，方便去重
sort.Ints(nums)
res := nums[0] + nums[1] + nums[2]
// 2. 计算 a + b + c 的值，不断留下最接近 target 的
for k:=0; k < len(nums) -2; k++ {
// ① a
if k > 0 && nums[k] == nums[k-1] {
continue
}
// 3. 转为 twoSumClosest
// 寻找 b + c >> target - a
tmp := twoSumClosest(nums, k+1, len(nums) -1, target - nums[k])
// 4. 不断记录更靠近 target 的 a + b + c
if math.Abs(float64(tmp + nums[k] - target)) <
math.Abs(float64( res - target)) {
res = tmp + nums[k]
}
}
return res
}
func twoSumClosest(nums []int, start, end, target int) int {
res := nums[start] + nums[end]
start ++
// nums 有序，可用双指针
for ;start < end; {
// 不断记录更靠近 target 两数之和
if math.Abs(float64( nums[start] + nums[end] - target)) <
math.Abs(float64( res - target)) {
res = nums[start] + nums[end]
}
// 往更可能靠近 target 的方向移动
if nums[start] + nums[end] <= target {
start++
} else {
end--
}
}
return res
}