type
status
date
slug
summary
tags
category
icon
password
想象一下
📝 两数之和经典写法
正常解法
想一想这个问题 一个数组 两个数的和等于 目标数 那就返回下标对吧
那就俩 循环去找 对应每个元素的组合 那这在数学上算是 对吧
比如说是 数字 a=[a1,a2,a3,a4]
那我们的想法的循环就是 这里直接 1234 代表 a1 a2 a3 a4
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
对吧 我们这是
但是不知道你有没有发现
这是对称矩阵 而且返回值 我们需要的是不同位置的那我们只需要半个的求和
21
31 32
41 42 43
也就是计算6次 而不是16次对吧
6是什么呢？是下半矩阵的数目，也就是说其组合是多少 对吧
对角线元素有几个呢？当然是n个对吧 让我们先减去n 那两边对称的一半就是
算一下16-4=12除以2 =6 对吧
想想是不是这样 长度为3
11 12 13
21 22 23
31 32 33
我们需要计算的和是什么呢？
21
31 32
看只需要3次发现没有 明白了吧 9-3=6除以2=3
那其实其复杂度就是这个了
我们想一下怎么去计算
看看长度为3的
21
31 32
当我们写代码 两次循环去实现去看 i j分别每次循环的值是多少呢？
这样写不太容易看出来
我们这么看
12 13 23
看出来了吗 3 是数组长度
01 02 12 对吧
那我们去循环
i=0 j=1;
i=0 j=2;
i=1 j=2; 结束
发现了吗
i从0开始 j从i+1开始且小于数组长度
那让我们来实现吧！
过了但是很菜啊 但是内存使用超了 83.4还行吧
想想怎么优化呢？
还是不行
就这吧 前面的太变态了
开玩笑的 真不玩了？
想想什么 是O1 不管内存了炸就炸吧
秒了 如图
- Author:徐昊
- URL:http://xuhao.help/article/2cc72ca2-6595-8011-9ed8-e82b3f5d874f
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
