两数之和 I 简单、两数之和 II 简单
NO.1 两数之和 简单
思路一：暴力法 看到题，最先想到的思路就是暴力解法，直接两层for循环遍历：
1
2
3
4
5
6
7
8
9
10
| public int[] twoSum(int[] nums,int target){
for (int i=0;i<nums.length;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 result!");
}
|
时间复杂度：O(n^2)
思路二：哈希表法 通过一个哈希表来空间换时间：1.遍历nums数组，判断每个元素和目标值的差temp是否在哈希表中。2.如果在就返回当前遍历元素的下标和哈希表中temp这个key对应的value。3.如果不在就将当前遍历元素作为key、当前遍历元素下标作为value存入哈希表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int[] twoSum(int[] nums,int target){
Map<Integer,Integer> map =new HashMap<Integer,Integer>();
for (int i=0;i<nums.length;i++){
int temp=target-nums[i];
if (map.containsKey(temp)){
return new int[]{map.get(temp),i};
}
map.put(nums[i],i);
}
throw new IndexOutOfBoundsException("no twoSum result!");
}
|
时间复杂度：O(n) 空间复杂度：O(n)
NO.167 两数之和 II 简单
思路一：双指针 双指针遍历数组，如果第 i 个元素加第 j 个元素的和 sum 等于 target 返回[i+1,j+1]；
如果 sum > target 说明需要更小的数字，则 j– ；如果 sum < target 说明需要更大的数字，则 i++ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum == target) {
return new int[]{i + 1, j + 1};
} else if (sum > target) {
j--;
} else {
i++;
}
}
throw new IllegalArgumentException();
}
|
时间复杂度：O(n)
本人菜鸟，有错误请告知，感激不尽！
更多题解和学习记录博客:博客、github