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++) {
if (elementToIndex.containsKey(target - nums[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！
