1. Two Sum
https://leetcode.com/problems/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].
point : 排序，二分查找
如何高效检查一个数组中是否包含某个值。 Arrays.sort 排序，然后用Arrays.binarySearch的方法
public class Solution1 {
public static int[] twoSum(int[] numbers, int target) {
int[] num = numbers.clone();
Arrays.sort(num);
int size = num.length;
int[] answers = new int[2];
for(int i=0;i<size;i++) {
if(Arrays.binarySearch(num, target-num[i])>0) {
int count=0,index1 = 0,index2=0;
for(int j=0;j<size;j++) {
if(numbers[j]==num[i]||numbers[j]==target-num[i]) {
count++;
if(count==2) {
index2=j;
answers[0] = (index1<index2?index1:index2)+1;
answers[1] = (index1>index2?index1:index2)+1;
break;
}
else {
index1=j;
}
}
}
}
}
return answers;
}
}
public class Solution2 {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int difference = target - nums[i];
if (map.containsKey(difference) && (map.get(difference)!=i)) {
result[1] = map.get(difference)+1;
result[0] = i + 1;
break;
}
}
return result;
}
}
public class Solution3 {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
if (map.get(numbers[i]) != null) {
int[] result = {map.get(numbers[i]), i };
return result;
}
map.put(target - numbers[i], i);
}
int[] result = {};
return result;
}
}
8