每天一题LeetCode [第二天]

每天一题LeetCode[第二天]

ToSum

Description:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Example:

解题过程：

首先题意十分简单易懂，给你一个整数类型的数组，在给你一个整数target，找出相加等于target的两个数的indices。

第一个思路就是穷举查找满足条件的两个数，时间复杂度o(n^2)，这是谁都能想到的思路，最好的结果肯定不是这样。优化：基于这样的思路，去除不可能的结果把数组中大于target的数去掉 减少n的值，但是这种复杂度也是o(n^2) 在细想，发现，只要基于这样的思想是没办法继续优化的。必须发现target 与两个结果 之间的特殊关系。

看了top solution 真是佩服！怎么说呢，这样吧，a+b=c 那么如果说对于nums来说，在遍历过程中能提前知道每个数字相对于c的补数，并且知道这个数的下表，那么这一切就很简单了。 因为是a+b=c 所以不用担心一次循环会错过结果，因为一定会经过a 和b的。 当经过a的时候 就记录下b的值 和 a的下标 这样在经过b的时候就知道 喔这就是我要的答案。 细想了一下，就是让每一步计算 的结果都有意义，相比于第一个结果很明显的是，第一种思路 ，每一步的计算意义都是为了从总的可能数中减去一，或者可以这样说，每一步的计算 之间关联不大，所以每一步的计算都显得繁琐。而第二种的思路，把每一步的计算的信息保存下来，对下一次的计算都起到了极大的帮助，大大简化了计算量。

top solution对java集合类很熟悉，运用了map的数据结构特点（索引快，），虽然增加了存储空间，但是时间复杂度在这个时代才是关键。

Java代码：

提高代码质量就是：每天积累精美的思路，优质的细节的过程。