萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第18题-四数之和

发表于 2022-04-03 | 分类于 力扣刷题 | 0 | 阅读次数 105

题目描述

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

题目评估

官方难度:中等
知识点:数组、双指针、排序

分析

四数之和加起来等于指定值,暴力需要四重循环时间肯定不够,那可以排序后让最里层两层循环双指针遍历,最外两层依然暴力遍历,并且因为是排序后的数组,在每层循环中可以跳过和上次重复的数字。

Java代码题解

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new LinkedList<>();
        int len = nums.length;
        if (len < 4) {
            return res;
        }
        Arrays.sort(nums);
        // 如果最小的四个数加起来都大于目标值就没有答案
        if ((long)nums[0] + nums[1] + nums[2] + nums[3] > target) {
            return res;
        }
        // 如果最大的四个数加起来仍小于目标值也没有正确答案
        if ((long)nums[len - 1] + nums[len - 2] + nums[len - 3] + nums[len - 4] < target) {
            return res;
        }
        // 从后向前遍历
        for (int i = len - 1; i >= 3; i--) {
            if (i != len - 1 && nums[i] == nums[i + 1]) {
                continue;
            }
            for (int j = i - 1; j >= 2; j--) {
                // 去重
                if (j != i - 1 && nums[j] == nums[j + 1]) {
                    continue;
                }
                // 当最外两层却确定时,与剩余两个最小的值加起来都大于目标值,说明最外两层的数字太大了,直接continue第二层
                if ((long)nums[i] + nums[j] + nums[0] + nums[1] > target) {
                    continue;
                }
                // 当最外两层却确定时,与剩余两个最大的值加起来都小于目标值,说明以后再也没有能加起来等于目标值的了,直接结束
                if ((long)nums[i] + nums[j] + nums[j - 1] + nums[j - 2] < target) {
                    break;
                }
                // 定义双指针
                int x = 0;
                int y = j - 1;
                while (x < y) {
                    // 求和
                    int sum = nums[i] + nums[j] + nums[x] + nums[y];
                    if (sum == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[x]);
                        list.add(nums[y]);
                        res.add(list);
                    }
                    // 滑动指针
                    if (sum > target) {
                        y--;
                        while (x < y && nums[y] == nums[y + 1]) {
                            y--;
                        }
                    } else {
                        x++;
                        while (x < y && nums[x] == nums[x - 1]) {
                            x++;
                        }
                    }
                }
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度:O(n^3),其中 n 是数组的长度。排序的时间复杂度是 O(nlogn),枚举四元组的时间复杂度是 O(n^3),因此总时间复杂度为 O(n^3 + nlogn) = O(n^3)。
空间复杂度:O(logn),其中 n 是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组 nums,实际情况中不一定允许,因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序,空间复杂度为O(n)。

# 算法 # 程序设计 # 力扣
力扣第19题-删除链表的倒数第N个节点
力扣第20题-有效的括号
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持