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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解决
方法1：暴力
class Solution {
public int[] twoSum(int[] nums, int target) {
//给一个integer的数组，和一个期望值，返回能得到期望值的下标。每一个元素不能用多次。
//第一想法是直接使用暴力法，一个个遍历，O（n^2）
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};
}
}
}
return null;
}
}
方法2：hash
class Solution {
public int[] twoSum(int[] nums, int target) {
//第二个思路是用hash存当前数字，用目标值减去当前数值，查看剩下的数值在不在map中。O(n)
Map<Integer, Integer> map = new HashMap();
for(int i = 0; i < nums.length; i ++) {
int val = target - nums[i];
if(map.containsKey(val)) {
return new int[]{map.get(val), i};
}
map.put(nums[i], i);
}
return null;
}
}
方法3：排序双指针
class Solution {
public int[] twoSum(int[] nums, int target) {
//查看别人的代码，第三个思路是使用排序双指针, O(n*logn)
//需要基于数组是已排序的，从两边向内收缩，直到找到命中的值。
//如果nums[L] + nums[R] >= target，则R--；相反则R++。
Node[] nodes = new Node[nums.length];
for(int i = 0; i < nums.length; i ++)
nodes[i] = new Node(i, nums[i]);
Arrays.sort(nodes, (o1, o2) -> o1.val - o2.val);
int L = 0, R = nums.length -1;
while(L < R) {
if(nodes[L].val + nodes[R].val == target) {
return new int[]{nodes[L].index, nodes[R].index};
}
else if(nodes[L].val + nodes[R].val > target) {
R --;
}
else {
L ++;
}
}
return null;
}
class Node {
int index;
int val;
public Node(int index, int val){
this.index = index;
this.val = val;
}
}
}