哈希算法专栏二《力扣题目练习》

引言

在了解了哈希表的基础理论之后，我们就可以开始进行刷题实战了。下面是我在力扣上找的一些题目，认真刷完并理解下面的题目，相信读者至少可以初步掌握哈希算法的思想了。

LeetCode242有效的字母异位词

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 字符怎么办？你能否调整你的解法来应对这种情况？

解题思路

由于s和t都是只包含小写字母的，字符a到字符z的ASCII也是26个连续的数值，因此只需要定义一个大小为26的数组作为哈希表。这个数组用来存储t字符串中每个字符出现的次数。因此我们需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。遍历字符串s，用数组记录字符串s中的每个字符出现的次数，然后再遍历字符串t，每遍历到一个字符就取哈希表中去找对应下标的值减一，最后遍历哈希表，如果哈希全为0就返回true，否则返回false。

代码

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

LeetCode349两个数组的交集

349. 两个数组的交集

已解答

简单

相关标签

相关企业

给定两个数组?nums1?和?nums2?，返回?它们的交集?。输出结果中的每个元素一定是?唯一?的。我们可以?不考虑输出结果的顺序?。

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

解题思路

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序。

由于题目限制了nums1[i]和nums2[i]的数值大小，因此我们可以使用数组作为哈希表。

那么如果题目没有限制nums1[i]和nums2[i]的数值大小时我们该怎么办呢？

这个时候我们就需要使用另外一种哈希数据结构HashSet了

代码

限制数值大小的情况，可以使用数组作为哈希表

 public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash1=new int[1002];
        int[] hash2=new int[1002];
        for (int i : nums1) {
            hash1[i]++;
        }
        for (int i : nums2) {
            hash2[i]++;
        }
        List<Integer> res=new ArrayList<>();
        for (int i = 0; i <1002; i++) {
            if (hash2[i]>0&&hash1[i]>0){
                res.add(i);
            }
        }
        int size = res.size();
        int[] result=new int[size];
        int index=0;
        for (Integer re : res) {
            result[index++]=re;
        }
        return result;
    }

没有限制数组大小时，使用HashSet

  public int[] intersection1(int[] nums1, int[] nums2) {
        if (nums1==null|| nums1.length==0||nums2==null||nums2.length==0) return new int[0];
        Set<Integer> set1=new HashSet<>();
        Set<Integer> resSet=new HashSet<>();
        for (int i : nums1) {
            set1.add(i);
        }
        for (int i : nums2) {
            if (set1.contains(i)){
                resSet.add(i);
            }
        }
        int size=resSet.size();
        int[] result=new int[size];
        int index=0;
        for (Integer integer : resSet) {
            result[index++]=integer;
        }
        return result;
    }

LeetCode202快乐数

202. 快乐数

已解答

简单

相关标签

相关企业

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

「快乐数」?定义为：

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

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

示例 1：

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

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 231 - 1

解题思路

题目中说了会?无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用HashSet了。

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

代码

   public boolean isHappy(int n) {
        if(n==1) return true;
        n=getHappy(n);
        return n==1;
    }

    private int getHappy(int n) {
        Set<Integer> hashSet=new HashSet<>();
        while (true){
            int[] sum=new int[32];
            int index=0;
            while (n>0){
                sum[index++]=n%10;
                n=n/10;
            }
            n=0;
            for (int i : sum) {
                n+=i*i;
            }
            if (hashSet.contains(n)){
                return n;
            }
            if (n==1) return n;
            hashSet.add(n);
        }
    }

LeetCode383赎金信

383. 赎金信

已解答

简单

相关标签

相关企业

给你两个字符串：ransomNote?和?magazine?，判断?ransomNote?能不能由?magazine?里面的字符构成。

如果可以，返回?true?；否则返回?false?。

magazine?中的每个字符只能在?ransomNote?中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote?和?magazine?由小写英文字母组成

解题思路

这道题目和242.有效的字母异位词?(opens new window)很像，242.有效的字母异位词?(opens new window)相当于求 字符串a 和 字符串b 是否可以相互组成 ，而这道题目是求 字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。

本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点。

• 第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思”? 这里说明杂志里面的字母不可重复使用。

• 第二点 “你可以假设两个字符串均只含有小写字母。”?说明只有小写字母，这一点很重要。

代码

暴力解法

那么第一个思路其实就是暴力枚举了，两层for循环，不断去寻找，代码如下：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (int i = 0; i < magazine.length(); i++) {
            for (int j = 0; j < ransomNote.length(); j++) {
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
            return true;
        }
        return false;
    }
};

• 时间复杂度: O(n^2)
• 空间复杂度: O(1)

这里时间复杂度是比较高的，而且里面还有一个字符串删除也就是erase的操作，也是费时的，当然这段代码也可以过这道题。

哈希解法

因为题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。

然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

依然是数组在哈希法中的应用。

一些读者可能想，用数组干啥，都用map完事了，其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // shortcut
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        // 定义一个哈希映射数组
        int[] record = new int[26];

        // 遍历
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }

        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }
        
        // 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }
}

LeetCode1两数之和

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)?的算法吗？

解题思路

很明显暴力的解法是两层for循环查找，时间复杂度是O(n^2)。

建议读者做这道题目之前，先做一下这两道

• 242. 有效的字母异位词(opens new window)
• 349. 两个数组的交集(opens new window)

242. 有效的字母异位词?(opens new window)这道题目是用数组作为哈希表来解决哈希问题，349. 两个数组的交集?(opens new window)这道题目是通过set作为哈希表来解决哈希问题。

首先我再强调一下?什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。

那么我们就应该想到使用哈希法了。

因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。

我们选用java中的HashMap作为容器进行存储遍历。接下来需要明确两点：

• map用来做什么
• map中key和value分别表示什么

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

代码

public class LeetCode1 {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if(nums == null || nums.length == 0){
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];   // 遍历当前元素，并在map中寻找是否有匹配的key
            if(map.containsKey(temp)){
                res[1] = i;
                res[0] = map.get(temp);
                break;
            }
            map.put(nums[i], i);    // 如果没找到匹配对，就把访问过的元素和下标加入到map中
        }
        return res;
    }
}

LeetCode454四数相加Ⅱ

454. 四数相加 II

已解答

中等

相关标签

相关企业

给你四个整数数组?nums1、nums2、nums3?和?nums4?，数组长度都是?n?，请你计算有多少个元组?(i, j, k, l)?能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

??提示：

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

解题思路

本题乍眼一看好像和0015.三数之和?(opens new window)，0018.四数之和?(opens new window)差不多，其实差很多。

本题是使用哈希法的经典题目，而0015.三数之和?(opens new window)，0018.四数之和?(opens new window)并不合适使用哈希法，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。

而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！

如果本题想难度升级：就是给出一个数组（而不是四个数组），在这里找出四个元素相加等于0，答案中不可以包含重复的四元组，大家可以思考一下，后续的文章我也会讲到的。

本题解题步骤：

1. 首先定义 一个HashMap，key放a和b两数之和，value 放a和b两数之和出现的次数。
2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
4. 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5. 最后返回统计值 count 就可以了

代码

public class LeetCode454 {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res=0;
        Map<Integer,Integer> map=new HashMap<>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int i1 : nums2) {
                int sum=i+i1;
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int i1 : nums4) {
                if (map.containsKey(-(i+i1))){
                    res+=map.get(-(i+i1));
                }
            }
        }
        return res;
    }
}

LeetCode15三数之和

15. 三数之和

已解答

中等

相关标签

相关企业

提示

给你一个整数数组?nums?，判断是否存在三元组?[nums[i], nums[j], nums[k]]?满足?i != j、i != k?且?j != k?，同时还满足?nums[i] + nums[j] + nums[k] == 0?。请

你返回所有和为?0?且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

解题思路

哈希解法

两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。

把符合条件的三元组放进ArrayList中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。

去重的过程不好处理，有很多小细节，如果在面试中很难想到位。

时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。

大家可以尝试使用哈希法写一写，就知道其困难的程度了。

双指针法

其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。

而且使用哈希法 在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长 。

接下来我来介绍另一个解法：双指针法，这道题目使用双指针法 要比哈希法高效一些，那么来讲解一下具体实现的思路。

动画效果如下：

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

时间复杂度：O(n^2)。

写这个题目还有一个关键问题，那就是该如何去重呢？

a的去重:

说到去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]

a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。

但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。

有同学可能想，这不都一样吗。

其实不一样！

都是和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。

如果我们的写法是 这样：

if (nums[i] == nums[i + 1]) { // 去重操作
    continue;
}

那我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。

我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！

所以这里是有两个重复的维度。

那么应该这么写：

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

b与c的去重

        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]));
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }

代码

哈希法

    public List<List<Integer>> threeSum1(int[] nums){
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);//先进行排序
        // 找出a + b + c = 0
        // a = nums[i], b = nums[j], c = -(a + b)
        for (int i = 0; i <nums.length; i++) {
            // 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
            if (nums[i]>0){
                break;
            }
            //三元组元素a去重
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            Set<Integer> set=new HashSet<>();
            for (int j = i+1; j <nums.length ; j++) {
                 // 三元组元素b去重
                if (j>i+1&&nums[j]==nums[j-1]&&nums[j-1]==nums[j-2]){
                    continue;
                }
                int c=0-(nums[i]+nums[j]);
                if (set.contains(c)){
                    List<Integer> sum=new ArrayList<>();
                    sum.add(nums[i]);
                    sum.add(nums[j]);
                    sum.add(c);
                    result.add(sum);
                    set.remove(c);
                }
                else {
                    set.add(nums[j]);
                }
            }
        }
        return result;
    }

双指针法

public class LeetCode15 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                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]));
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

LeetCode18四数之和

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

解题思路

四数之和，和15.三数之和?(opens new window)是一个思路，都是使用双指针法, 基本解法就是在15.三数之和?(opens new window)的基础上再套一层for循环。

但是有一些细节需要注意，例如： 不要判断nums[k] > target?就返回了，三数之和 可以通过?nums[i] > 0?就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

15.三数之和?(opens new window)的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

代码

class LeetCode18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; i++) {
		
            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }
		
            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {

                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
		    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}