Two Sum I II III

1. Two Sum 1
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].
不排序,给特定target,问数组里是否有两数之和与target相等。
利用hashmap, key存每个数或者target与数的差值,value存index

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                break;
            }else{
                map.put(nums[i], i);
            }
        }
        return result;
    }
}

2. Two Sum II
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
简单方法利用双指针,比和大,尾指针–,比和小头指针++;提高效率可以结合binary search,比和大,判断中点加头指针,如果仍然比头大,尾指针直接移到中点,另一半同理。

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int start = 0;
        int end = numbers.length - 1;
        int[] result = new int[2];
        while(start + 1< end){
            int middle = start + (end - start)/2;
            if((numbers[start] + numbers[end]) < target){
                if((numbers[middle] + numbers[end]) == target){
                    start = middle;
                    break;
                }else if(numbers[middle] + numbers[end] < target){
                    start = middle + 1;
                }else{
                    start++;
                }
                
            }else if((numbers[start] + numbers[end]) > target){
                if((numbers[start] + numbers[middle]) == target){
                    end = middle;
                    break;
                }else if(numbers[middle] + numbers[start] > target){
                    end = middle - 1;
                }else{
                    end--;
                }
            }else{
                break;
            }
        }
        result[0] = start + 1;
        result[1] = end + 1;
        return result;
    }
}

3.Two Sum III
Design and implement a TwoSum class. It should support the following operations: add and find.

add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
利用一个hashmap,key是每一个数,value是每个数出现的次数。当要组成target的两个数相等是,要确定这个是是不是在map里有不止一个

public class TwoSum {

    /** Initialize your data structure here. */
    Map<Integer, Integer> map;
    public TwoSum() {
        map = new HashMap<Integer, Integer>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if(map.containsKey(number)){
            map.put(number, map.get(number) + 1);
        }else{
            map.put(number, 1);
        }
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            int i = entry.getKey();
            int j = value - i;
            if((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))){
                return true;
            }
        }
        return false;
    }
}