1.Two Sum I

1.Description(Easy)

Given an array of integers, find two numbers such that they add up to a specific target number.

The functiontwoSumshould 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) areNOTzero-based.

Notice

You may assume that each input would have exactly one solution

Example

numbers=[2, 7, 11, 15], target=9

return[1, 2]

Challenge

Either of the following solutions are acceptable:

• O(n) Space, O(nlogn) Time

• O(n) Space, O(n) Time

2.Code

Version 1: Sort+Two pointers(空间上更好)--O(nlogn)--Time limit exceed

先排序，head在头，tail在尾。

sum>target --> tail--

sum<target --> head++

 public int[] twoSum(int[] numbers, int target) {
        if(numbers==null || numbers.length==0){
            return null;
        }
        int[] result=new int[2];
        Arrays.sort(numbers);
        int head=0;
        int tail=numbers.length-1;
        while(head<tail){
            int sum=numbers[head]+numbers[tail];
            if(sum>target){
                tail--;
            }
            else if(sum<target){
                head++;
            }
            else{
                result[0]=head;
                result[1]=tail;    
            }
        }
        return result;
    }

Version 2: HashMap(时间上更好) O(n)

public int[] twoSum2(int[] numbers, int target){
        if(numbers==null || numbers.length==0){
            return null;
        }
        int[] result=new int[2];
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<numbers.length;i++){
            if(!map.containsKey(numbers[i])){
                map.put(target-numbers[i], i);
            }else{
                //both index1 and index2) are NOT zero-based.
                result[0]=i+1;
                result[1]=map.get(numbers[i])+1;
            }
        }
        Arrays.sort(result);
        return result;
    }

可以通过一个哈希表减少时间复杂度：

int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    HashMap<Integer, Integer> index = new HashMap<>();
    // 构造一个哈希表：元素映射到相应的索引
    for (int i = 0; i < n; i++)
        index.put(nums[i], i);
    
    for (int i = 0; i < n; i++) {
        int other = target - nums[i];
        // 如果 other 存在且不是 nums[i] 本身
        if (index.containsKey(other) && index.get(other) != i)
            return new int[] {i, index.get(other)};
    }
    
    return new int[] {-1, -1};
}

这样，由于哈希表的查询时间为 O(1)，算法的时间复杂度降低到 O(N)，但是需要 O(N) 的空间复杂度来存储哈希表。不过综合来看，是要比暴力解法高效的。

我觉得 Two Sum 系列问题就是想教我们如何使用哈希表处理问题。

Extend:

(Retuers phone interview):

no sorted arrays, have duplicates,return the number of pairs

先用一个hashmap记录值和他们出现的次数。

载一次遍历数组，如果target-array[i]存在，就把他们的数量相乘就是他们pair的数量。

比如{1,1,1,1,3,3,4,5} target=4,对于1,3这个pair来说有4*2=8对。

但是这里有个特殊情况，target-array[i] == array[i]

比如{4,4,4,4,4,5,6,7} target=8;

对于4,4 这个pair来说，按照上面的做法是5*5 = 25. 所以这种情况应该是 5*(5-1)/2 = 10

public int twosum(int[] array, int target){
        if (array == null || arrays.length == 0) {
            return 0;
        }

        int result = 0;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int i = 0; i<arrays.length; ++i) {
            int current = array[i];
            if(!map.containsKey(current)) {
                map.put(current,1);
            }else{
                map.put(current, map.get(current)+1);
            }
        }

        for (int i = 0; i < array.length; ++i) {
            if(target - array[i] == array[i]) {
                int cnt = map.get(array[i]);
                if(cnt > 1) result += cnt*(cnt-1)/2;
                map.remove(array[i]);
            }else{
                if(map.containsKey(target - array[i])){
                    result += map.get(target - array[i])*map.get(array[i]);
                    map.remove(array[i]);
                    map.remove(target-array[i]);
                }
            }
        }
        return result;
    }

对于这个题目，如果array非常大。但是是reachable的，最好的应该是O(nlogn) sort,再用two pointer去做。

Two pointers:

while (lo < hi) {
    int sum = nums[lo] + nums[hi];
    // 记录索引 lo 和 hi 最初对应的值
    int left = nums[lo], right = nums[hi];
    if (sum < target)      lo++;
    else if (sum > target) hi--;
    else {
        res.push_back({left, right});
        // 跳过所有重复的元素
        while (lo < hi && nums[lo] == left) lo++;
        while (lo < hi && nums[hi] == right) hi--;
    }
}

这样就可以保证一个答案只被添加一次，重复的结果都会被跳过，可以得到正确的答案。不过，受这个思路的启发，其实前两个 if 分支也是可以做一点效率优化，跳过相同的元素：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    // nums 数组必须有序
    sort(nums.begin(), nums.end());
    int lo = 0, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        int left = nums[lo], right = nums[hi];
        if (sum < target) {
            while (lo < hi && nums[lo] == left) lo++;
        } else if (sum > target) {
            while (lo < hi && nums[hi] == right) hi--;
        } else {
            res.push_back({left, right});
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return res;
}