锐客网

  1. 首页 > 睿知 > it技术 > >

螺旋矩阵java代码 螺旋矩阵java实现( 六 )

IT技术unicode


时间复杂度：O(n2)
题目：18. 四数之和 ()
难度：简单
描述：
给定一个包含 n 个整数的数组 nums 和一个目标值 target ， 判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组 。
注意：答案中不可以包含重复的四元组 。
题目示例
思路：
我们延续三数之和的思路，在三数之和外面再套一层循环 。
时间复杂度：O(n3)
题目：209. 长度最小的子数组()
难度：中等
描述：
给定一个含有 n 个正整数的数组和一个正整数 target。
找出该数组中满足其和target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度 。如果不存在符合条件的子数组，返回 0。
题目示例
思路
这道题是一道经典的滑动窗口问题[4] 。
image-20210801164436322
代码如下：
时间复杂度：O(n)，虽然循环里套循环了，但是starrt和end各自被移动了n次 ， 所以时间复杂度是O(n) 。
题目：219. 存在重复元素 II ()
难度：简单
描述：
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k 。
题目示例
思路：
上面我们做了一道滑动窗口的题，我们接着再做一道也可以用滑动窗口解决的问题 。
这道题的滑动窗口略有区别 ， 上一道题的窗口是活动的，这个是固定的滑动窗口 ,维护一个长度为k的固定窗口，如果窗口内含有目标值，返回 。如果窗口进入新的元素，就需要把头部的元素移除掉 ， 保持窗口的长度 。
固定窗口
代码如下：
时间复杂度：O(n) 。
题目：1052. 爱生气的书店老板()
难度：中等
描述：
今天 ， 书店老板有一家店打算试营业 customers.length 分钟 。每分钟都有一些顾客（customers[i]）会进入书店 ， 所有这些顾客都会在那一分钟结束后离开 。
在某些时候，书店老板会生气 。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1 ， 否则 grumpy[i] = 0 。当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的 。
书店老板知道一个秘密技巧 ， 能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次 。
请你返回这一天营业下来，最多有多少客户能够感到满意 。
「示例：」
思路：
这道题是一道固定窗口的问题 。
整体思路就是把不生气的部分作为固定窗口，固定窗口把customers分成了三部分，最后求三部分的最大和 。
固定窗口
时间复杂度：O(n) 。
空间复杂度：O(1) 。
题目：面试题3. 数组中重复的数字 ()
难度：复杂
描述：
找出数组中重复的数字 。
在一个长度为 n 的数组 nums 里的所有数字都在 0 n-1 的范围内 。数组中某些数字是重复的，但不知道有几个数字重复了 ， 也不知道每个数字重复了几次 。请找出数组中任意一个重复的数字 。
「示例 1：」
思路：
「哈希法」
这种找重复的数字问题，我们脑子里第一下就想起来，用Hash存储元素 ， 然后进行比对 。
代码实现也很简单：
时间复杂度：O(n) 。
空间复杂度：O(n)
但今天的主角不是它，而是
「原地置换法」
我们注意到一个条件所有数字都在 0 n-1 的范围内 ,那就在这方面进行操作，我们可以把元素放到它的值对应的下标的位置 。

推荐阅读


上一篇：gislog表示的简单介绍

下一篇：玩具直播间投放技巧，玩具直播间装修图