哈希——18. 四数之和

简介: 本专栏按照数组—链表—哈希—字符串—栈与队列—二叉树—回溯—贪心—动态规划—单调栈的顺序刷题,采用代码随想录所给的刷题顺序,一个正确的刷题顺序对算法学习是非常重要的,希望对大家有帮助

1 题目描述

  1. 四数之和

给你一个由 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
你可以按 任意顺序 返回答案 。

2 题目示例

示例 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]]

3 题目提示

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

4 思路

排序 + 双指针

最朴素的方法是使用四重循环枚举所有的四元组,然后使用哈希表进行去重操作,得到不包含重复四元组的最终答案。假设数组的长度是n,则该方法中,枚举的时间复杂度为O(n4),去重操作的时间复杂度和空间复杂度也很高,因此需要换—种思路。为了避免枚举到重复四元组,则需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素,且在同一重循环中不能多次枚举到相同的元素。
为了实现上述要求,可以对数组进行排序,并且在循环过程中遵循以下两点:

  • 每—种循环枚举到的下标必须大于上—重循环枚举到的下标;
  • 同—重循环中,如果当前元素与上一个元素相同,则跳过当前元素。

使用上述方法,可以避免枚举到重复四元组,但是由于仍使用四重循环,时间复杂度仍是o(n4)。注意到数组已经被排序,因此可以使用双指针的方法去掉一重循环。

使用两重循环分别枚举前两个数,然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。假设两重循环枚举到的前两个数分别位于下标i和j,其中i<j。初始时,左右指针分别指向下标j+1和下标n―1。每次计算四个数的和,并进行如下操作:

  • 如果和等于target,则将枚举到的四个数加到答案中,然后将左指针右移直到遇到不同的数,将右指针左移直到遇到不同的数;
  • 如果和小于target,则将左指针右移一位;
  • 如果和大于target,则将右指针左移一位。

使用双指针枚举剩下的两个数的时间复杂度是O(n),因此总时间复杂度是o(n3),低于O(n')。

具体实现时,还可以进行一些剪枝操作:

  • 在确定第一个数之后,如果nums[i]+ nums[i+1]+nums[i+2]+ nums[i+3] > target,说明此时剩下的三个数无论取什么值,四数之和一定大于 target,因此退出第—重循环;
  • 在确定第一个数之后,如果 nums[i] + nums[n — 3]+nums[n —2] + nums[n ―1]<target,说明此时剩下的三个数无论取什么值,四数之和一定小于target,因此第一重循环直接进入下一轮,枚举nums[i+1];
  • 在确定前两个数之后,如果nums[司+ nums[ij]+ numsl[j+1]+ nums[j+2] > target,说明此时剩下的两个数无论取什么值,四数之和一定大于target,因此退出第二重循环;
  • 在确定前两个数之后,如果nums[i]+ nums[j]+nums[n — 2]+nums[n ― 1]<target,说明此时剩下的两个数无论取什么值,四数之和一定小于target,因此第二重循环直接进入下一轮,枚举nums[j+1]。

5 我的答案

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
            return quadruplets;
        }
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.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] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}
相关文章
|
6月前
《LeetCode》—— 哈希
《LeetCode》—— 哈希
|
6月前
|
算法 C语言
OJ刷题:求俩个数组的交集(没学哈希表?快排双指针轻松搞定!)
OJ刷题:求俩个数组的交集(没学哈希表?快排双指针轻松搞定!)
|
11月前
|
算法 测试技术 C#
C++二分算法:使数组严格递增
C++二分算法:使数组严格递增
|
5月前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
33 1
|
算法 数据安全/隐私保护 索引
【数据结构与算法】哈希表2:四数相加II & 赎金信 & 三数之和 & 四数之和
【数据结构与算法】哈希表2:四数相加II & 赎金信 & 三数之和 & 四数之和
74 0
|
算法
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
题目要求斐波那契数列长度要大于等于3,就等于说要确定 x[1] 和 x[2]来确定x[3]…x[n]之和的数列,所以我们用两层for循环来枚举x[1] 和 x[2] ,因为斐波那契数列满足 x[i] = x[i - 1] + x[i - 2], 所以x[3] = x[1] + x[2] x[4] = x[3] + x[2]…,我们只需要三个变量来不断变换, 每次从 arr 中找前两个数,然后查看后续在符合斐波那契的数在arr中是否存在
106 0
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
|
C++ 容器
力扣349 - 两个数组的交集【哈希表+数组+双指针】
对应力扣349.两个数组的交集,三种思路三个方向,带你玩转LeetCode
133 0
力扣349 - 两个数组的交集【哈希表+数组+双指针】
|
算法 C语言 容器
力扣260 - 只出现一次的数字||| 【哈希映射、异或位运算+分治思想】
对应力扣260.只出现一次的数字|||,包含哈希映射和异或位运算+分治思想两种解法,超详细步骤讲解
159 0
力扣260 - 只出现一次的数字||| 【哈希映射、异或位运算+分治思想】
|
存储 索引
leetcode【哈希表—简单】1.两数之和
leetcode【哈希表—简单】1.两数之和
leetcode【哈希表—简单】1.两数之和
leetcode【哈希表—中等】454.四数相加 II
leetcode【哈希表—中等】454.四数相加 II
leetcode【哈希表—中等】454.四数相加 II