【LeetCode】两数之和、三数之和、四数之和系列

r囧r小猫 2022-12-26 04:49 203阅读 0赞

### 文章目录 ###

*   *   *  两数之和★
         *  三数之和★★
         *  四数之和★★
         *  四数相加Ⅱ★★
         *  最接近的三数之和★★

--------------------

此篇文章总结下力扣中的两数之和、三数之和、四数之和及一系列求数组中满足达到目标值的元组个数的问题，仔细阅读下面的出题形式和解法，不难想到解决这类问题的思路无非是**排序数组后进行相应的数组分组，双指针查找、二分法查找、或者哈希表记录**。

在此说明以下题解有些是自己刷题时的思路，有些是热评，还有官方题解或者热门题解。最终版权归力扣官方所有，如有侵权敬请告知。

### 两数之和★ ###

[LeetCode两数之和链接][LeetCode]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

**解题思路**：每遍历一个元素，哈希表中保存target与已遍历元素的差和相应的下标，若哈希表中存在此元素，则找到符合条件的解，否则将差值和相应下标加入哈希表

具体代码如下：

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
            for(int i = 0; i<nums.length; i++){
        
                if(hash.containsKey(nums[i])){
        
                    return (new int[] {
        i, hash.get(nums[i])});
                }
                hash.put(target - nums[i], i);
            }
            return null;
        }
    }

**时间复杂度**：O（n）

### 三数之和★★ ###

[LeetCode三数之和链接][LeetCode 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

**解题思路**：对数组排序后，使用双指针，并进行适当的剪枝，具体见代码

或者排序后，双重循环+二分查找也是一种思路

class Solution {
        
        public List<List<Integer>> threeSum(int[] nums) {
        
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null || nums.length < 3) {
        
                return res;
            }
            Arrays.sort(nums);
            for(int i = 0; i < nums.length - 2; i++) {
        
                if(i > 0 && nums[i] == nums[i - 1]) {
        
                    continue;
                }
                if(nums[i] + nums[i + 1] + nums[i + 2] > 0) {
        
                    break;
                }
                //双指针
                int le = i + 1, ri = nums.length - 1;
                while(le < ri) {
        
                    int sum = nums[i] + nums[le] + nums[ri];
                    if(sum == 0) {
        
                        res.add(Arrays.asList(nums[i], nums[le], nums[ri]));
                        le++;
                        while(le < ri && nums[le] == nums[le - 1]) {
        
                            le++;
                        }
                        //此处先减1再执行循环可以避免越界（这样处理边界更合适）
                        ri--;
                        while(le < ri && nums[ri] == nums[ri + 1]) {
        
                            ri--;
                        }
                    }else if(sum < 0) {
        
                        le++;
                    }else {
        
                        ri--;
                    }
                }
            }
            return res;
        }
    }

**时间复杂度**：O（n²）

### 四数之和★★ ###

[LeetCode四数之和链接][LeetCode 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]

**解题思路**：同三数之和一样，双重for循环 + 双指针 + 剪枝

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

**时间复杂度**：O（n³）

### 四数相加Ⅱ★★ ###

[LeetCode四数相加Ⅱ链接][LeetCode 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 3]

**解题思路**：先对每个数组排序，然后将A和B划分为一组，使用哈希表保存**差值及差值个数**（可以有相同元组，一个数组中有相同元素或不同数组有相同元素），将C和D划分为一组，其两两划分后和题目两数之和的思路一样

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

**时间复杂度**：O（n²）

### 最接近的三数之和★★ ###

[LeetCode最接近的三数之和链接][LeetCode 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 4]

**解题思路**：与三数之和思路相同，排序后使用双指针，因为是求最接近的，所以要使用做差后求绝对值来判断接近程度

以下思路及代码来自力扣热评[qiyexue][]

class Solution {
        
        public int threeSumClosest(int[] nums, int target) {
        
            Arrays.sort(nums);
            int N = nums.length;
            int closestSum = nums[0] + nums[1] + nums[2];
            for(int i = 0; i < N - 2; i++) {
        
                int le = i + 1, ri = N - 1;
                while(le < ri) {
        
                    int threeSum = nums[i] + nums[le] + nums[ri];
                    if(Math.abs(threeSum - target) < Math.abs(closestSum - target)) {
        
                        closestSum = threeSum;
                    }
                    if(threeSum < target) {
        
                        le++;
                    }else if(threeSum > target) {
        
                        ri--;
                    }else {
        
                        return target;
                    }
                }
            }
            return closestSum;
        }
    }

**时间复杂度**：O（n²）

[LeetCode]: https://leetcode-cn.com/problems/two-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a1864272a5324d9690bbbfee51652439.png
[LeetCode 1]: https://leetcode-cn.com/problems/3sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/70b8d03cc37645aaa9970e08576385c6.png
[LeetCode 2]: https://leetcode-cn.com/problems/4sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/240e2bf0f0df4cf7b6b29b67b26538f2.png
[LeetCode 3]: https://leetcode-cn.com/problems/4sum-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/3f02b31af6924502abe2b896d64641f0.png
[LeetCode 4]: https://leetcode-cn.com/problems/3sum-closest/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/a5d8b521fb2849a994a65f29e224842f.png
[qiyexue]: https://leetcode-cn.com/u/qiyexue/