分析

这个题目可以说是一目了然，直接能够想到的解法就是遍历这一个序列，然后遍历下标大于当前遍历到的数字的元素，如果有匹配的数字就直接返回结果即可。

如果单纯遍历，时间复杂度高达O(n²)，这个复杂度不太令人满意。

那么是否可以通过空间换时间呢？自然是没问题的。

后续考虑通过使用HashMap的方式记录每个值对应的元素的下标，每次检查是否有当前值相加得到目标值的的key存在，将时间复杂度降低到了O(n)，不过空间复杂度也上升到了O(n)。

解法

public class Solution {
    public int[] twoSum(int[] nums, int target) {
                Map<Integer, Integer> numIdxMap = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; ++i) {
            numIdxMap.put(nums[i], i);
        }

        int[] idx = new int[2];

        for (int i = 0; i < nums.length; ++i) {
            if (numIdxMap.containsKey(target - nums[i])) {
                int j = numIdxMap.get(target - nums[i]);

                if (i == j) {
                    continue;
                }

                idx[0] = i;
                idx[1] = j;

                if (idx[0] > idx[1]) {
                    int tmp = idx[1];
                    idx[1] = idx[0];
                    idx[0] = tmp;
                }

                break;
            }
        }

        return idx;
    }
}

public class Solution {

public int[] twoSum(int[] nums, int target) {

Map<Integer, Integer> numIdxMap = new HashMap<Integer, Integer>();

for (int i = 0; i < nums.length; ++i) {

numIdxMap.put(nums[i], i);

}

int[] idx = new int[2];

for (int i = 0; i < nums.length; ++i) {

if (numIdxMap.containsKey(target - nums[i])) {

int j = numIdxMap.get(target - nums[i]);

if (i == j) {

continue;

}

idx[0] = i;

idx[1] = j;

if (idx[0] > idx[1]) {

int tmp = idx[1];

idx[1] = idx[0];

idx[0] = tmp;

}

break;

}

return idx;

}

起因

OJ在学生时代应该都有所接触，作为程序设计与算法课程的实践内容也在一些OJ上做过少数的一些题目。不得不说，多年的习惯让在OJ上解题成为了一件很愉悦的事情。

工作后，原本薄弱的算法知识感觉消失殆尽，尽管在每天的工作中，组装、修改成为了工作的主题，可是总觉得自己不应如此，希望自己能保持毕业前那样积极的学习态度，希望自己能把之前的自主学习和思考的习惯保持下来。然而自己在每天的工作之后，惰性还是占了上风，阅读自然不少，可是这类基础的训练却扔下了。

本科期间由于学校身边的环境的缘故，自学了Java的基础编程。这半年对Android开发很感兴趣，再次接触Java，自己实现的过程中，感觉自己再次的丢掉了很多东西。

工作两年，经历了最开始的模仿、学习阶段之后，也尝试了各个方向，单独承担系统的开发维护工作中，更是觉得基础的知识，诸如网络、OS等基础知识在解决问题上能对思路起到打磨的作用，避免自己掉进 case by case 的坑里。积累经验当然重要，但是个人觉得更难得的是学会如何找到解决问题的方式，面向StackOverflow编程并不是一个好的选择。

近期看到 云风 大牛的关于反转单向链表微博，自己下班尝试编写了一下，也是花了一会儿时间才能顺畅的写完。这两天也是看到liaohuqiu 大牛发起的 LeetCode攻克计划，觉得是时候重新开始修行了。

目的

刷 LeetCode 的目的主要有两个：

从基础开始，重新学习Java编程
重新学习算法知识

第一个理由可能引人发笑，然而这确实是一个手段。自己在学习编写Java程序的过程中曾经过分的贪图速度，跳过了很多自认为基础的语言上的内容，在比较自己编写的代码与熟练的同事的代码中，更能有所体会。

计划

基于第一个原因，所有的LeetCode解题都会使用Java完成。

目前来看，一共有83道 Easy 题目，167道 Medium 题目，以及74道 Hard 题目。

不求过分贪心，希望半年内，我能把所有的 Easy 完成。

对于解决的题目，将会在blog里贴出自己的解题方案以及简要的解题思路，同时在解题过程中，尽量通过完备自己的思路和case解决问题，而不是通过尝试AC来解决问题。

已解决问题 [2]

two-sum Easy

add-two-numbers Medium

Wislay

标签归档：LeetCode

LeetCode-1

概述

分析

解法

尝试LeetCode

起因

目的

计划

已解决问题 [2]