桂林北站改造最新方案,无锡网站制作.,google官方网站注册,网络制作软件其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一#xff1a;双指针排序
三、代码
3.1 方法一#xff1a;双指针排序
3.2 方法二#xff1… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一双指针排序
三、代码
3.1 方法一双指针排序
3.2 方法二两次遍历 hash 法
3.3 方法三一次遍历 hash 法
四、复杂度分析
4.1 方法一双指针排序
4.2 方法二两次遍历 hash 法
4.3 方法三一次遍历 hash 法 前言
这是力扣的 1679 题难度为中等解题方案有很多种本文讲解我认为最奇妙的一种。 一、题目描述
给你一个整数数组 nums 和一个整数 k 。
每一步操作中你需要从数组中选出和为 k 的两个整数并将它们移出数组。
返回你可以对数组执行的最大操作数。
示例 1 输入nums [1,2,3,4], k 5
输出2
解释开始时 nums [1,2,3,4]
- 移出 1 和 4 之后 nums [2,3]
- 移出 2 和 3 之后 nums []
不再有和为 5 的数对因此最多执行 2 次操作。 示例 2 输入nums [3,1,3,4,3], k 6
输出1
解释开始时 nums [3,1,3,4,3]
- 移出前两个 3 之后nums [1,4,3]
不再有和为 6 的数对因此最多执行 1 次操作。提示
1 nums.length 1051 nums[i] 1091 k 109 二、题解
本题其实有很多种解法比方说两次遍历 hash 法一次遍历 hash 法但这些方法都不如双指针排序法简洁干练销量也没双指针排序法高。 两次遍历 hash 法时间复杂度O(n),空间复杂度O(n)。 一次遍历 hash 法时间复杂度O(n),空间复杂度O(n)。 双指针排序法时间复杂度O(nlogn n),空间复杂度O(1)。 但按理说排序的时间复杂度是大于 hash 的但是他的代码效率反而更高说明 hash 算法的效率太低或者冲突严重。
在下面我也会贴两次遍历 hash 法和一次遍历 hash 法的代码解题思路就不讲解了。 2.1 方法一双指针排序
思路与算法
1. 首先先将数组排序在设定左右指针 i 和 j 分别指向数组的头和尾。 2. 将两个指针指向的数进行求和
若和大于目标则说明太大了需要右指针左移可以使和变小。若和小于目标则说明太小了需要左指针右移可以使和变大。若和等于目标则两个指针都往中间移动结果 1 。
3. 循环2步骤直至左指针不在右指针的左边。 三、代码
3.1 方法一双指针排序
Java版本
class Solution {public int maxOperations(int[] nums, int k) {int count 0, i 0, j nums.length - 1;Arrays.sort(nums);while (i j) {if (nums[i] nums[j] k) {count;i;j--;} else if (nums[i] nums[j] k) {j--;} else {i;}}return count;}
}
C版本
#include algorithm
#include vectorclass Solution {
public:int maxOperations(std::vectorint nums, int k) {int count 0;std::sort(nums.begin(), nums.end());int i 0, j nums.size() - 1;while (i j) {if (nums[i] nums[j] k) {count;i;j--;} else if (nums[i] nums[j] k) {j--;} else {i;}}return count;}
};Python版本
class Solution:def maxOperations(self, nums: List[int], k: int) - int:count 0nums.sort()i, j 0, len(nums) - 1while i j:if nums[i] nums[j] k:count 1i 1j - 1elif nums[i] nums[j] k:j - 1else:i 1return count3.2 方法二两次遍历 hash 法
Java版本
class Solution {public int maxOperations(int[] nums, int k) {MapInteger, Integer map new HashMap(nums.length);//统计每个数据出现的次数key为数据value为次数for (int num : nums) {Integer i map.getOrDefault(num, 0);map.put(num, i 1);}int result 0;for (int num : nums) {// 求和达到K的数据int x k - num;// 从map获取xint i map.get(num);//如果次数小于等于0说明数据被使用过了【就算后面遍历到他也可以跳过了】if (i 0) {continue;}//统计数量减一先减去防止两个相同的数据相加达到K而只有一个数据//【有个大兄弟有疑问为什么直接删了。补充一下因为是两遍循环第一次就统计过所有的数据了如果后面的if无法进入那么之后也不可能了删了就删了无所谓了。】map.put(num, i - 1);// 是否有 另一个数据。且统计的数量大于0if (map.containsKey(x) map.get(x) 0) {result;//结果1map.put(x, map.get(x) - 1);// 数量减一}}return result;}
}
3.3 方法三一次遍历 hash 法
Java版本
class Solution {public int maxOperations(int[] nums, int k) {MapInteger, Integer map new HashMap(nums.length);int result 0;//统计每个数据出现的次数key为数据value为次数for (int num : nums) {// 获取求和的另一个数int x k - num;// 从map获取xInteger i map.get(x);// 是否有 另一个数据。且统计的数量大于0if (i ! null map.get(x) 0) {result;//结果1map.put(x, map.get(x) - 1);// 数量减一continue;}//这个数没有被使用统计数量1Integer count map.getOrDefault(num, 0);map.put(num, count 1);}return result;}
} 四、复杂度分析
4.1 方法一双指针排序
时间复杂度O(nlogn n)。空间复杂度O(1)。
4.2 方法二两次遍历 hash 法
时间复杂度O(n)。空间复杂度O(n)。
4.3 方法三一次遍历 hash 法
时间复杂度O(n)。空间复杂度O(n)。
