leetcode——查找表相关问题

清疚 2022-09-02 11:40 189阅读 0赞

### leetcode——查找表相关问题 ###

*  
 *   *  349. 两个数组的交集
     *  350. 两个数组的交集 II
     *  242. 有效的字母异位词
     *  202. 快乐数
     *  290. 单词规律
     *  1. 两数之和
     *  15. 三数之和
     *  18. 四数之和
     *  16. 最接近的三数之和
     *  454. 四数相加 II
     *  49. 字母异位词分组
     *  447. 回旋镖的数量
     *  149. 直线上最多的点数
     *  219. 存在重复元素 II
     *  217. 存在重复元素
     *  220. 存在重复元素 III

#  #

睡不着啊，难受，随便写写。

## 349. 两个数组的交集 ##

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
输出：\[2\]

示例 2：

输入：nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\]  
输出：\[9,4\]

说明：

输出结果中的每个元素一定是唯一的。
    我们可以不考虑输出结果的顺序。

解法：用两个set，一个存第一个数组的，遍历第二个数组，判断是否在set1中，是则加入set2。

class Solution {
        
        public int[] intersection(int[] nums1, int[] nums2) {
        
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> set2 = new HashSet<>();
            for(int num: nums1){
        
                set1.add(num);
            }
            for(int num: nums2){
        
                if(set1.contains(num)){
        
                    set2.add(num);
                }
            }
            int[] res = new int[set2.size()];
            int i = 0;
            for(int num : set2){
        
                res[i++] = num;
            }
            return res;
        }
    }

## 350. 两个数组的交集 II ##

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
输出：\[2,2\]

示例 2:

输入：nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\]  
输出：\[4,9\]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
    我们可以不考虑输出结果的顺序。

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
    如果 nums1 的大小比 nums2 小很多，哪种方法更优？
    如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解法：将nums1用map存起来，然后遍历一遍nums2,把相同的存到list中。

class Solution {
        
        public int[] intersect(int[] nums1, int[] nums2) {
        
            Map<Integer, Integer> map1 = new HashMap<>();
            List<Integer> resultList = new ArrayList<>();
            for(int num: nums1){
        
                map1.put(num, map1.getOrDefault(num, 0) + 1);
            }
            for(int num: nums2){
        
                if(map1.containsKey(num)){
        
                    resultList.add(num);
                    map1.put(num, map1.get(num) - 1);
                    if(map1.get(num) == 0){
        
                        map1.remove(num);
                    }
                }
            }
            int[] result = new int[resultList.size()];
            for(int i = 0; i < resultList.size(); i++){
        
                result[i] = resultList.get(i);
            }
            return result;
        }
    }

## 242. 有效的字母异位词 ##

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”  
输出: true

示例 2:

输入: s = “rat”, t = “car”  
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
    s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解法一：最直接的想法就是用map存第一个字符串，然后遍历第二个字符串的字符来判断是否在map中，在则value-1。

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            Map<Character, Integer> map = new HashMap<>();
            for(int i = 0; i < s.length(); i++){
        
                char c = s.charAt(i);
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            for(int i = 0; i < t.length(); i++){
        
                char c = t.charAt(i);
                if(map.containsKey(c)){
        
                    map.put(c, map.get(c) - 1);
                    if(map.get(c) == 0)
                        map.remove(c);
                }else{
        
                    return false;
                }
            }
            return map.size() == 0;
        }
    }

但是效率好像不太行啊  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70]改进：  
解法二：用一个新的数组，int\[\] cnt = new int\[26\]， 遍历一遍字符串，进行 ++cnt\[s.charAt(i) - ‘a’\]; 和 --cnt\[t.charAt(i) - ‘a’\]; 如果最后结果cnt数组中有任何一个值不为0，则返回false；

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            if(s.length() != t.length())
                return false;
            int[] cnt = new int[26];
            for(int i = 0; i < s.length(); i++){
        
                cnt[s.charAt(i) - 'a'] ++;
                cnt[t.charAt(i) - 'a'] --;
            }
            for(int i = 0; i < cnt.length; i++){
        
                if(cnt[i] != 0){
        
                    return false;
                }
            }
            return true;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70 1]emmm好了一点点，勉强吧。  
解法三：直接排序，比对对应位置的字符。

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            if(s.length() != t.length())
                return false;
            char[] ss = s.toCharArray();
            char[] tt = t.toCharArray();
            Arrays.sort(ss);
            Arrays.sort(tt);
            return Arrays.equals(ss, tt);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70 2]可以了可以了。

## 202. 快乐数 ##

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
    然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
    如果 可以变为  1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

输入：19  
输出：true  
解释：  
12 + 92 = 82  
82 + 22 = 68  
62 + 82 = 100  
12 + 02 + 02 = 1

示例 2：

输入：n = 2  
输出：false

提示：

1 <= n <= 231 - 1

解法：  
解决两个问题：①计算sum ②如何判断重复。

class Solution {
        
        public boolean isHappy(int n) {
        
            int sum;
            Set<Integer> set = new HashSet<>();
            while(n != 1){
        
                if(!set.contains(n)){
        
                    set.add(n);
                }else{
        
                    return false;
                }
                sum = 0;
                while(n != 0){
        
                    int mul = n % 10;
                    n = n / 10;
                    sum += mul * mul;
                }
                n = sum;
            }
            return true;
        }
    }

## 290. 单词规律 ##

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = “abba”, str = “dog cat cat dog”  
输出: true

示例 2:

输入:pattern = “abba”, str = “dog cat cat fish”  
输出: false

示例 3:

输入: pattern = “aaaa”, str = “dog cat cat dog”  
输出: false

示例 4:

输入: pattern = “abba”, str = “dog dog dog dog”  
输出: false

说明:  
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母

解法：通过字符和字符串映射即可，做的时候没想过map有containsValue这个函数，涨见识了。

class Solution {
        
        public boolean wordPattern(String pattern, String s) {
        
            Map<Character, String> map = new HashMap<>();
            char[] c = pattern.toCharArray();
            String[] ss = s.split(" ");
            if(c.length != ss.length)
                return false;
            for(int i = 0; i < c.length; i++){
        
                if(map.containsKey(c[i])){
        
                    if(!map.get(c[i]).equals(ss[i]))
                        return false;
                }else if(map.containsValue(ss[i])){
        
                    return false;
                }
                map.put(c[i], ss[i]);
            }
            return true;
        }
    }

1.  同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = “egg”, t = “add”  
输出：true

示例 2：

输入：s = “foo”, t = “bar”  
输出：false

示例 3：

输入：s = “paper”, t = “title”  
输出：true

提示：

可以假设 s 和 t 长度相同。

解法和上一道题一模一样。

class Solution {
        
        public boolean isIsomorphic(String s, String t) {
        
            if(s.length() != t.length())
                return false;
            char[] ss = s.toCharArray();
            char[] tt = t.toCharArray();
            Map<Character, Character> map = new HashMap<>();
            for(int i = 0; i < ss.length; i++){
        
                if(map.containsKey(ss[i])){
        
                    if(map.get(ss[i]) != tt[i]){
        
                        return false;
                    }
                }else if(map.containsValue(tt[i])){
        
                    return false;
                }
                map.put(ss[i], tt[i]);
            }
            return true;
        }
    }

## 1. 两数之和 ##

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 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 <= 104
    -109 <= nums[i] <= 109
    -109 <= target <= 109
    只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            Map<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < nums.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,0};
        }
    }

## 15. 三数之和 ##

给你一个包含 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.  怎么解决重复的问题：判断nums\[i\] == nums\[i - 1\]，如果是则跳过。
2.  怎么初始化返回的list，调用Arrays的asList方法，new ArryaList<>(Arrays.asList(xx,xx));

class Solution {
        
        public List<List<Integer>> threeSum(int[] nums) {
        
            // [-4, -1, -1, 0, 1, 2]
            List<List<Integer>> res = new ArrayList<>();
            int n = nums.length;
            if(n < 3){
        
                return res;
            }
            Arrays.sort(nums);
            for(int i = 0; i < n; i++){
        
                if(nums[i] > 0){
        
                    break;
                }
                int lo = i + 1;
                int hi = n - 1;
                if(i > 0 && nums[i] == nums[i - 1])
                    continue;
                while(lo < hi){
        
                    int sum = nums[i] + nums[lo] + nums[hi];
                    if(sum < 0){
        
                        lo++;
                    }else if(sum > 0){
        
                        hi--;
                    }else{
        
                        res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[lo], nums[hi])));
                        while(lo < hi && nums[lo] == nums[++lo]);
                        while(lo < hi && nums[hi] == nums[--hi]);
                    }
                }
            }
            return res;
        }
    }

## 18. 四数之和 ##

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 \[nums\[a\], nums\[b\], nums\[c\], nums\[d\]\] ：

0 <= a, b, c, d < n
    a、b、c 和 d 互不相同
    nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = \[1,0,-1,0,-2,2\], target = 0  
输出：\[\[-2,-1,1,2\],\[-2,0,0,2\],\[-1,0,0,1\]\]

示例 2：

输入：nums = \[2,2,2,2,2\], target = 8  
输出：\[\[2,2,2,2\]\]

提示：

1 <= nums.length <= 200
    -109 <= nums[i] <= 109
    -109 <= target <= 109

解法：跟上一道题一样的思路

class Solution {
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
        
            List<List<Integer>> res = new ArrayList<>();
            int n = nums.length;
            if(n < 4)
                return res;
            Arrays.sort(nums);
            for(int i = 0; i < n; i++){
        
                if(i > 0 && nums[i] == nums[i - 1])
                        continue;
                for(int j = i + 1; j < n - 1; j++){
        
                    int lo = j + 1;
                    int hi = n - 1;
                    if(j > i + 1 && nums[j] == nums[j - 1])
                        continue;
                    while(lo < hi){
        
                        int sum = nums[i] + nums[j] + nums[lo] + nums[hi];
                        if(sum < target){
        
                            lo++;
                        }else if(sum > target){
        
                            hi--;
                        }else{
        
                            res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[lo], nums[hi])));
                            while(lo < hi && nums[lo] == nums[++lo]);
                            while(lo < hi && nums[hi] == nums[--hi]);
                        }
                    }   
                }
            }
            return res;
        }
    }

## 16. 最接近的三数之和 ##

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = \[-1,2,1,-4\], target = 1  
输出：2  
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3
    -10^3 <= nums[i] <= 10^3
    -10^4 <= target <= 10^4

class Solution {
        
        public int threeSumClosest(int[] nums, int target) {
        
            Arrays.sort(nums);
            int ans = nums[0] + nums[1] + nums[2];
            for(int i = 0; i < nums.length; i++){
        
                int lo = i + 1;
                int hi = nums.length - 1;
                while(lo < hi){
        
                    int sum = nums[i] + nums[lo] + nums[hi];
                    if(Math.abs(target - sum) < Math.abs(target - ans)){
        
                        ans = sum;
                    }
                    if(sum < target){
        
                        lo++;
                    }else if(sum > target){
        
                        hi--;
                    }else{
        
                        return ans;
                    }
                }
            }
            return ans;
        }
    }

## 454. 四数相加 II ##

给定四个包含整数的数组列表 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

解法：按照常规的解法，四个数组遍历需要O（n ^ 4）,如果将一个数组放进查找表，需要O（n ^ 3）, 如果把nums1和nums2的和放进查找表，则需要O（n ^ 2）。

class Solution {
        
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        
            Map<Integer, Integer> map = new HashMap<>();
            for(int a : nums1){
        
                for(int b : nums2){
        
                    map.put(a + b, map.getOrDefault(a + b, 0) + 1);
                }
            }
            int res = 0;
            for(int c : nums3){
        
                for(int d : nums4){
        
                    if(map.containsKey(-c-d)){
        
                        res += map.get(-c-d);
                    }
                }
            }
            return res;
        }
    }

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

给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词指字母相同，但排列不同的字符串。

示例 1:

输入: strs = \[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”\]  
输出: \[\[“bat”\],\[“nat”,“tan”\],\[“ate”,“eat”,“tea”\]\]

示例 2:

输入: strs = \[""\]  
输出: \[\[""\]\]

示例 3:

输入: strs = \[“a”\]  
输出: \[\[“a”\]\]

提示：

1 <= strs.length <= 104
    0 <= strs[i].length <= 100
    strs[i] 仅包含小写字母

解法: 用一个map存String和字母异位词的集合。

class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            Map<String, List<String>> map = new HashMap<>();
            for(String str : strs){
        
                char[] s = str.toCharArray();
                Arrays.sort(s);
                String ss = new String(s);
                List<String> list = map.getOrDefault(ss, new ArrayList<>());
                list.add(str);
                map.put(ss, list);
            }
            return new ArrayList<>(map.values());
        }
    }

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

给定平面上 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

提示：

n == points.length
    1 <= n <= 500
    points[i].length == 2
    -104 <= xi, yi <= 104
    所有点都 互不相同

解法：可以以i为基准点，计算每个点跟i之间的距离。用一个map保存dis和相同dis的个数。若个数为1，则无距离相同的点，为2则有 2 \* 1个相同。 为 3 则有 3\*2=6个，依次类推。（对于距离公式，我们一般算根号的，但是这里只是用来比较，我们可以以平方值来比较即可。）其他点到枢纽点的距离，对于距离可以用距离的平方，就不会出现小数。

class Solution {
        
        public int numberOfBoomerangs(int[][] points) {
        
            int res = 0;
            for(int i = 0; i < points.length; i ++){
        
                Map<Integer, Integer> map = new HashMap<>();
                for(int j = 0; j < points.length; j++){
        
                    if(i != j){
        
                        int sum = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0])
                        + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
    
                        map.put(sum, map.getOrDefault(sum, 0) + 1);
                    }
                }
                for(int val : map.values()){
        
                    res +=  val * (val - 1);
                }
            }
            return res;
        }
    }

## 149. 直线上最多的点数 ##

给你一个数组 points ，其中 points\[i\] = \[xi, yi\] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

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

示例 2：

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

提示：

1 <= points.length <= 300
    points[i].length == 2
    -104 <= xi, yi <= 104
    points 中的所有点 互不相同

解法：这道题比较难，要解决的问题有：  
1.用map保存斜率和点数，最后输出点数最大的值，要如何对map的values进行排序。  
用一个  
2.斜率求法得用除，如果我们直接运算会有精度问题。

class Solution {
        
        public int maxPoints(int[][] points) {
        
            // 用map存斜率和点数。
            if(points.length < 2)
                return points.length;
            int res = 0;
            for(int i = 0; i < points.length; i++){
        
                Map<String, Integer> lines = new HashMap<>();
                int tmp_max = 0;
                for(int j = 0; j < points.length; j++){
        
                    int dy = points[i][1] - points[j][1];
                    int dx = points[i][0] - points[j][0];
                    // 算最小公约数是要将结果值相同的映射到一个字符串中，比如 3/6=2/4=1/2;
                    int g = gcd(dy, dx);
                    if(g != 0){
        
                        dy /= g;
                        dx /= g;
                    }
                    String tmp = String.valueOf(dy) + "/" + String.valueOf(dx);
                    lines.put(tmp, lines.getOrDefault(tmp, 0) + 1);
                    // 依次更新，解决map中values排序的问题
                    tmp_max = Math.max(tmp_max, lines.get(tmp));
                    // 这个+1是由于上面当两点斜率若第一次出现时，只存入1, 如果这就是结果显然得返回2（两个点）。
                    res = Math.max(res, tmp_max + 1);
                }
            }
            return res;
        }
        private int gcd(int dy, int dx){
        
            if(dx == 0) return dy;
            else return gcd(dx, dy % dx);
        }
    }

## 219. 存在重复元素 II ##

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums \[i\] = nums \[j\]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

输入: nums = \[1,2,3,1\], k = 3  
输出: true

示例 2:

输入: nums = \[1,0,1,1\], k = 1  
输出: true

示例 3:

输入: nums = \[1,2,3,1,2,3\], k = 2  
输出: false

class Solution {
        
        public boolean containsNearbyDuplicate(int[] nums, int k) {
        
            Set<Integer> set = new HashSet<>();
            for(int i = 0; i < nums.length; i++){
        
                // 维护一个大小为k的set，如果在set中存在该值，则返回true；
                if(!set.add(nums[i])){
        
                    return true;
                }
                if(set.size() > k){
        
                    // 移除掉最先进入set的。
                    set.remove(nums[i - k]);
                }
            }
            return false;
        }
    }

## 217. 存在重复元素 ##

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: \[1,2,3,1\]  
输出: true

示例 2:

输入: \[1,2,3,4\]  
输出: false

示例 3:

输入: \[1,1,1,3,3,4,3,2,4,2\]  
输出: true

class Solution {
        
        public boolean containsDuplicate(int[] nums) {
        
            Arrays.sort(nums);
            for(int i = 0; i < nums.length - 1; i++){
        
                if(nums[i] == nums[i + 1])
                    return true;
            }
            return false;
        }
    }

## 220. 存在重复元素 III ##

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums\[i\] - nums\[j\]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = \[1,2,3,1\], k = 3, t = 0  
输出：true

示例 2：

输入：nums = \[1,0,1,1\], k = 1, t = 2  
输出：true

示例 3：

输入：nums = \[1,5,9,1,5,9\], k = 2, t = 3  
输出：false

提示：

0 <= nums.length <= 2 * 104
    -231 <= nums[i] <= 231 - 1
    0 <= k <= 104
    0 <= t <= 231 - 1

不会。看懂了再来补充

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70]: /images/20220829/e19ba808c9a4480e85074d3cad3c86a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70 1]: /images/20220829/420b07cddf294da0b1207d80b9bd1949.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70 2]: /images/20220829/8516b716e3b24ff19ff2be24f9251f05.png