四数之和 (LeetCode 18)

简介: 四数之和 (LeetCode 18)

四数之和 (LeetCode 18)

Description

给你一个由 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

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

Sample Input 1

nums = [1,0,-1,0,-2,2], target = 0

Sample Output 1

[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Sample Input 2

nums = [2,2,2,2,2], target = 8

Sample Output 2

[[2,2,2,2]]

Tips

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

算法思想:

四数之和,和15.三数之和是一个思路,都是使用双指针法, 基本解法就是在三数之和的基础上再套一层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)就可以了。

三数之和的双指针解法是一层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) 。

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

对于三数之和双指针法就是将原本暴力O(n^3)的解法,降为O(n^2)的解法,四数之和的双指针解法就是将原本暴力O(n^4)的解法,降为O(n^3)的解法。

四数相加II是四个独立的数组,只要找到A[i] + B[j] + C[k] + D[l] = 0就可以,不用考虑有重复的四个元素相加等于0的情况,所以相对于本题还是简单了不少!

双指针法将时间复杂度:O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级,

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
                break; // 这里使用break,统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], 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++;

                        // 找到答案时,双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

补充:

二级剪枝的部分:

if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
    break;
}

可以优化为:

if (nums[k] + nums[i] > target && nums[i] >= 0) {
    break;
}

因为只要 nums[k] + nums[i] > target,那么 nums[i] 后面的数都是正数的话,就一定 不符合条件了。

不过这种剪枝 其实有点 小绕,大家能够理解 文章给的完整代码的剪枝 就够了。

Java代码代码如下:

class Solution {
    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;
    }
}

Created by Ss1Two on 2023/2/9

目录
相关文章
|
JSON API Android开发
Android bundetool 详解
Android bundetool 详解
325 0
|
机器学习/深度学习 编解码 并行计算
论文阅读笔记 | Transformer系列——CSWin Transformer
论文阅读笔记 | Transformer系列——CSWin Transformer
958 0
论文阅读笔记 | Transformer系列——CSWin Transformer
|
安全 测试技术
Fiddler入门教程全家桶,建议收藏
Fiddler入门教程全家桶,建议收藏
263 1
|
9月前
|
人工智能 Cloud Native Serverless
Serverless Devs 官网全新升级,Serverless+AI 重磅来袭
Serverless Devs 官网迎来全新升级,主站以 AI 应用开发的叙事透出项目特性和解决方案。应用中心(Registry)将各类热门 AI 应用模版、实用 AI 工具以及 AI 工作流等呈现给用户。本次升级主题为“一站式 AI/函数/应用开发”,希望为开发者提供更加便利的应用模版搜索和展示服务,本文将对本次升级的三大看点进行整理,欢迎您来体验!
|
9月前
|
负载均衡 芯片 异构计算
NSDI'24 | 阿里云飞天洛神云网络论文解读——《LuoShen》揭秘新型融合网关 洛神云网关
NSDI‘24于4月16-18日在美国圣塔克拉拉市举办,阿里云飞天洛神云网络首次中稿NSDI,两篇论文入选。其中《LuoShen: A Hyper-Converged Programmable Gateway for Multi-Tenant Multi-Service Edge Clouds》提出超融合网关LuoShen,基于Tofino、FPGA和CPU的新型硬件形态,将公有云VPC设施部署到边缘机柜中,实现小型化、低成本和高性能。该方案使成本降低75%,空间占用减少87%,并提供1.2Tbps吞吐量,展示了强大的技术竞争力。
|
XML 机器学习/深度学习 JSON
|
12月前
|
机器学习/深度学习 人工智能 自然语言处理
企业内训|LLM大模型技术在金融领域的应用及实践-某商业银行分行IT团队
本企业培训是TsingtaoAI技术团队专们为某商业银行分行IT团队开发的LLM大模型技术课程。课程深入分析大模型在金融行业中的发展趋势、底层技术及应用场景,重点提升学员在大模型应用中的实际操作能力与业务场景适应力。通过对全球商用 LLM 产品及国内外技术生态的深度对比,学员将了解大模型在不同企业中的发展路径,掌握如 GPT 系列、Claude 系列、文心一言等大模型的前沿技术。针对金融行业的业务需求,学员将学会如何结合多模态技术改进用户体验、数据分析等服务流程,并掌握大模型训练与工具链的实操技术,尤其是模型的微调、迁移学习与压缩技术。
404 2
|
存储 缓存 Java
Eureka原理与实践:深入探索微服务架构的核心组件
在微服务架构日益盛行的今天,服务之间的注册与发现成为了保证系统高可用性和灵活性的关键。Eureka,作为Netflix开源的服务注册与发现框架,凭借其简单、健壮的特性,在微服务领域占据了举足轻重的地位。本文将深入剖析Eureka的原理,并通过实践案例展示其在实际项目中的应用,以期为开发者提供一个高端、深入的视角。
177 0
|
存储 SQL 缓存
【MySQL】change buffer,buffer pool,redo log,bin log,undo log的作用
【MySQL】change buffer,buffer pool,redo log,bin log,undo log的作用
338 0
|
SQL 缓存 大数据
优化数据库性能的五大策略
传统的数据库性能优化常常集中在SQL查询优化和索引设计上,然而,在当今大数据时代,优化数据库性能需要综合考虑更多因素。本文将介绍五大策略,从硬件资源利用、数据模型设计、查询优化、缓存策略到数据库配置调整,为您提供全面的数据库性能优化方案。