LeetCode 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

大致意思就是给定一个整数数组，找出其中两个数满足相加等于指定的目标数字，返回这个两个数的数组下标。
同时题目还给出了一个隐含的条件：有且只有一个解 —— 数组中的元素不重复

有半年没刷题了，开始的时候没有好的思路，先用最笨的方法解决这个问题，二重循环，时间复杂度O(n^2)

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

        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((nums[j]) == target - nums[i]) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

提交通过之后，查看Editorial找到了更好的解法：使用HashMap，由element映射index，遍历至数组元素element时查找HashMap中是否已存在key等于target - element，若存在即可从HashMap中取出其下标，若不存在则向HashMap中装入(element, index)，这样只需遍历数组一次，而在HashMap中的每次查询时间复杂度均为O(1)，所以总的时间复杂度O(n)

import java.util.HashMap;

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

        int[] result = new int[2];
        Map<Integer, Integer> elementToIndex = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 避免target - nums[i] = nums[i]的情况
            if (elementToIndex.containsKey(target - nums[i]) && elementToIndex.get(target - nums[i]) < i) {
                result[0] = elementToIndex.get(target - nums[i]);
                result[1] = i;
                return result;
            }
            elementToIndex.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

以前几乎没在LeetCode上刷过题，现在题目总数已经增加到429道了，短时间内是刷不完了，刷题在精不在多，争取明年暑假之前把一些经典的题目多刷几遍。另外只用自带的编辑器写代码，坚决不用IDE！