Related Topics：[Array][Hash Table]
Similar Questions
[3Sum][4Sum][Two Sum II - Input array is sorted][Two Sum III - Data structure design][Subarray Sum Equals K][Two Sum IV - Input is a BST]
題目：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].
思路1
暴力搜索级乍，兩層循環(huán)遍歷數(shù)組進(jìn)行查找儡毕。該算法時(shí)間復(fù)雜度是O(n^2)。
java解法：
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i=0;i<nums.length-1;i++) {
for(int j=i+1;j<nums.length;j++) {
if(nums[i]+nums[j]==target) {
return new int[]{i,j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
思路二
本題目標(biāo)是對(duì)數(shù)組的元素值進(jìn)行判斷碎节，返回對(duì)應(yīng)值的索引號(hào)曾我，因此可以建立值-索引映射粉怕，用Map結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行查找。使用map的時(shí)間復(fù)雜度為O(n)抒巢。
方法一
使用兩層迭代贫贝，第一層將整個(gè)數(shù)組裝入Map結(jié)構(gòu)中，第二層在Map結(jié)構(gòu)中查找符合要求的key即元素值蛉谜，并返回對(duì)應(yīng)的value即元素索引稚晚。
java解法1
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++) {
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++) {
int complement=target-nums[i];
//此處要注意兩個(gè)值應(yīng)代表不同元素
if(map.containsKey(complement)&&i!=map.get(complement)) {
return new int[]{i,map.get(complement)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
方法二
可以將方法二中的兩次循環(huán)合為一個(gè)循環(huán)，一邊將元素及索引存入map結(jié)構(gòu)型诚，一遍查看map中是否已有與該元素相加為target的值客燕。
java解法2
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++) {
int complement=target-nums[i];
if(map.containsKey(complement)) {
return new int[]{map.get(complement),i};
}
map.put(nums[i],i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
