【LeetCode】查找表问题：特殊键值选择

╰+攻爆jí腚メ 2022-10-29 09:11 103阅读 0赞

### 灵活选择键值 ###

#### [454. 四数相加 II][454. _ II] ####

难度中等329收藏分享切换为英文接收动态反馈

给定四个包含整数的数组列表 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 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

**例如:**

输入:
    A = [ 1, 2]
    B = [-2,-1]
    C = [-1, 2]
    D = [ 0, 2]
    
    输出:
    2
    
    解释:
    两个元组如下:
    1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

**只能使用查找表，但是只对最内层查找表超时**

class Solution { 
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { 
            Map<Integer , Integer> record = new HashMap<>();
            for(int i = 0; i < D.length ; i ++){ 
                record.put(D[i] , record.getOrDefault(D[i] , 0) + 1);
            }
    
            int res = 0;
            for(int i = 0; i < A.length ; i ++){ 
                for(int j = 0 ; j < B.length ; j ++){ 
                    for(int k = 0 ; k < C.length ; k ++){ 
                        res += record.getOrDefault(0 - A[i] - B[j] - C[k] , 0);
                    }
                }
            }
    
            return res;
        }
    }

**对两层的和使用查找表**

class Solution { 
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { 
            Map<Integer , Integer> record = new HashMap<>();
            for(int i = 0 ; i < A.length ; i ++){ 
                for(int j = 0 ; j < B.length ; j ++){ 
                    record.put(A[i] + B[j] , record.getOrDefault(A[i] + B[j] , 0) + 1);
                }
            }
    
            int res = 0 ;
            for(int i = 0 ; i < C.length ; i ++){ 
                for(int j = 0 ; j < D.length ; j ++){ 
                    res += record.getOrDefault(0 - C[i] - D[j] , 0);
                }
            }
    
            return res;
        }
    }

#### [49. 字母异位词分组][49.] ####

难度中等652收藏分享切换为英文接收动态反馈

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

**示例:**

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
    输出:
    [
      ["ate","eat","tea"],
      ["nat","tan"],
      ["bat"]
    ]

**对 Map 的 KeySet 遍历查找超时**

class Solution { 
        public List<List<String>> groupAnagrams(String[] strs) { 
            Map<String , List<String>> record = new HashMap<>();
            for(String s : strs){ 
                boolean isAdd = false;
                for(String r : record.keySet()){ 
                    if(r.length() != s.length()){ 
                        continue;
                    }
    
                    Map<Character , Integer> sRecord = new HashMap<>();
                    for(int i = 0 ; i < s.length() ; i ++){ 
                        sRecord.put(s.charAt(i) , sRecord.getOrDefault(s.charAt(i) , 0) + 1);
                    }
                
                    boolean canAdd = true;
                    for(int i = 0 ;i < r.length() ; i ++){ 
                        if(sRecord.get(r.charAt(i)) == null || sRecord.get(r.charAt(i)) <= 0){ 
                            canAdd = false;
                            break;
                        }
                        sRecord.put(r.charAt(i) , sRecord.get(r.charAt(i)) - 1);
                    }
    
                    if(canAdd){ 
                        record.get(r).add(s);
                        isAdd = true;
                        break;
                    }
                }
    
                if(!isAdd){ 
                    List<String> list = new LinkedList<>();
                    list.add(s);
                    record.put(s , list);
                }
            }
    
            List<List<String>> res = new LinkedList<>();
            for(String pattern : record.keySet()){ 
                res.add(record.get(pattern));
            }
    
            return res;
        }
    }

**对字符排完序再查**

class Solution { 
        public List<List<String>> groupAnagrams(String[] strs) { 
            Map<String , List<String>> record = new HashMap<>();
            for(String s : strs){ 
                char[] sArr = s.toCharArray();
                Arrays.sort(sArr);
                String sortS = String.valueOf(sArr);
    
                if(record.get(sortS) != null){ 
                    record.get(sortS).add(s);
                }else { 
                    List<String> sortSList = new ArrayList<>();
                    sortSList.add(s);
                    record.put(sortS , sortSList);
                }
            }
    
            List<List<String>> res = new LinkedList<>();
            for(String pattern : record.keySet()){ 
                res.add(record.get(pattern));
            }
    
            return res;
        }
    }

#### [447. 回旋镖的数量][447.] ####

难度中等127收藏分享切换为英文接收动态反馈

给定平面上 `n` 对 **互不相同** 的点 `points` ，其中 `points[i] = [xi, yi]` 。**回旋镖** 是由点 `(i, j, k)` 表示的元组 ，其中 `i` 和 `j` 之间的距离和 `i` 和 `k` 之间的距离相等（**需要考虑元组的顺序**）。

返回平面上所有回旋镖的数量。

**示例 1：**

输入：points = [[0,0],[1,0],[2,0]]
    输出：2
    解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

**示例 2：**

输入：points = [[1,1],[2,2],[3,3]]
    输出：2

**示例 3：**

输入：points = [[1,1]]
    输出：0

**题解**

class Solution { 
        public int numberOfBoomerangs(int[][] points) { 
            int res = 0;
    
            for(int i = 0 ; i < points.length ; i ++){ 
                HashMap<Double , Integer> record = new HashMap<>();
                for(int j = 0 ; j < points.length ; j ++){ 
                    if(i == j){ 
                        continue;
                    }
                    double dest = Math.sqrt(Math.pow((points[i][0] - points[j][0]) , 2) + Math.pow((points[i][1] - points[j][1]) , 2));
                    if(record.get(dest) != null){ 
                        res = res + record.get(dest) * 2;
                    }
                    record.put(dest , record.getOrDefault(dest , 0 ) + 1);
                }
            }
    
            return res;
        }
    }

###  ###

class Solution { 
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { 
            int res = 0;
            for(int i = 0 ; i < nums.length ;  i ++){ 
                for(int j = i - 1 ; j >= Math.max(i - k, 0) ; j --){ 
                    long d = (long)nums[i] - (long)nums[j];
                    if(Math.abs(d) <= t){ 
                        res ++;
                    }
                }
            }
    
            return res != 0;
        }
    }

[454. _ II]: https://leetcode-cn.com/problems/4sum-ii/
[49.]: https://leetcode-cn.com/problems/group-anagrams/
[447.]: https://leetcode-cn.com/problems/number-of-boomerangs/