最近开始重拾算法, 在 LeetCode 上刷题. 顺便也记录下解题报告以及优化思路.
题目链接: 1. 两数之和 https://leetcode-cn.com/problems/two-sum/
题意
给定一个整数数组 nums? 和一个目标值 target, 请你在该数组中找出和为目标值的那? 两个? 整数, 并返回他们的数组下标.
你可以假设每种输入只会对应一个答案. 但是, 你不能重复利用这个数组中同样的元素.
示例:
nums = [2, 7, 11, 15], target = 9
返回 [0, 1]
题意很简单, 就是寻找两个数, 这两个数相加的值等于 target. 且保证每组输入一定会有答案.
解题思路
从题意上看, 只需要找到那两个数即可. 那么首先可以想到的就是枚举组合两个数的和, 但是 组合数 的数量是非常大的, 这个思路就可以作罢.
两个数相加的和等于 target, 反过来, 对于一个数 nums[i], 能否在数组里找到另外一个数 nums[j] 使得 nums[j] = target - nums[i]. 这样我们只需要关心一个数即可.
暴力枚举
简单粗暴, 一重循环用来枚举 nums[i], 另一重用来寻找 nums[j].
代码:
- public class Solution {
- public int[] TwoSum(int[] nums, int target) {
- for(int i = 0; i <nums.Length; i ++) {
- int res = target - nums[i];
- for(int j = 0; j < nums.Length; j ++) {
- if(i == j) continue;
- if(res == nums[j]) return new int[] {i, j};
- }
- }
- return new int[] {};
- }
- }
执行用时: 904ms
内存消耗: 29.6MB
用时排名: 超过 21.29%
29 个案例, 耗时近 1 秒. 由于这里仅有循环辅助变量, 内存消耗其实不大.
耗时排名是排在比较后面的, 这也说明了还有更优的解法.
空间换时间
此题关键的地方在于: 如何快速的找到 j, 暴力枚举在最坏的情况下会找遍整个数组, 直到最后一个才找到, 时间复杂度也就是 O(n).
那么, 在这里我们可以利用 哈希算法 进行映射, 从而达到更快查找效率. 理论上 哈希算法 设计良好的情况下可以达到 常数级 O(1) 的复杂度.
一个例子: 在值不大的情况下, 可以用值当做数组下标, 而数组的值作为原来数组的下标. 即:
对于 x = nums[i], 存在 hash[x] = i. 这样在牺牲大量空间的情况下可以使得查询效率达到极致的常数级 O(1).
但是很遗憾, 这道题并没有办法直接使用这个方法, 因为 int.MaxValue 是远超过了数组可以定义的范围. 编译时会报错, 内存溢出.
既然暂时没有办法达到 O(1) 的地步, 那么可以考虑使用实现了 哈希算法 (这里保留说法, 若羽源码没有阅读完, 在看到 index 的取法有着很明显的哈希痕迹进行猜测的) 的 Dictionary<TKey, TValue>.
代码:
- public class Solution
- {
- public int[] TwoSum(int[] nums, int target)
- {
- var dic = new Dictionary<int, List<int>>();
- for(int i = 0; i <nums.Length; i ++)
- {
- int num = nums[i];
- int res = target - num;
- if(dic.ContainsKey(res))
- {
- return new int[] {i, dic[res][0]};
- }
- if(!dic.ContainsKey(num))
- {
- dic.Add(num, new List<int>(){});
- }
- dic[num].Add(i);
- }
- return new int[] {};
- }
- }
执行用时: 468 ms
内存消耗: 30.5MB
用时排名: 超过 78.61%
改进后的算法排名与之前可谓是天差地别, 已经到了前 30%.
仅仅是达到了前三分之一, 说明这个算法还有可以更进一步的优化.
进一步优化查询
这里用了 Dictionary, 但这里的 TValue 是一个列表. 仔细想想, 这里我们是不需要保存列表的, 只需要保存一个值即可, 因为只需要找到一组答案即可!
其次可以减去第二个判断, 并不需要判断是否存在, 直接覆盖 / 新建即可.
最后可以反向查询, 查之前的数值中是否缺一个 nums[i], 对应存进去的就是差值, 这样可以减去两个临时变量, 顺带优化一点点的空间.
代码:
- public class Solution
- {
- Dictionary<int, int> dic = new Dictionary<int, int>();
- public int[] TwoSum(int[] nums, int target)
- {
- if(nums.Length == 2) return new int[] {0, 1};
- dic.Clear();
- for (int i = 0; i < nums.Length; i++)
- {
- if(dic.ContainsKey(nums[i])) return new int[] {dic[nums[i]], i};
- dic[target - nums[i]] = i;
- }
- return new int[] { };
- }
- }
执行用时: 360 ms
内存消耗: 30MB
用时排名: 超过 98.83%
改进后的算法相比之前的差距并不是非常的大, 但就是这百来毫秒的差距, 排名上升到了前 3%.
这个算法还是有可以改进的地方, 但是若羽现在暂时还没有思路如何再进一步将查询复杂度降下去, 这里可能需要自己实现一个更高效的哈希算法.
写在最后
许久没有接触算法了, 有些生疏, 思路上也有些堵塞. 这里若羽对于接下来进一步优化有一些初步的想法, 待有空实验后再加一篇解题报告.
分段策略, 当数据量达到一定程度时使用更高效的算法, 当数据量较小时, 可能哈希耗时会更长一些, 这个需要实验. 大意便是寻找多个算法的耗时阈值, 利用阈值进行策略选择.
自己实现针对题目更高效的哈希算法.
来源: http://www.bubuko.com/infodetail-3146300.html