Two Sum || LeetCode-1

2017-08-20 leetcode PV:

Problem link： https://leetcode.com/problems/3sum-closest/#/description

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 numbers = [2, 7, 11, 15], target = 9,

Because numbers[0] + numbers[1] = 2 + 7 = 9,

return [0, 1].


<问题描述>

给定一个整形数组，需要从数组中找出两个整数，使得它们的和等于另外一个给定的整数

你可以假定每一个输入有且仅有一个答案，并且不能使用同一个元素两次

给出的twoSum函数应该返回找到的这两个整数的索引值，而且index1必须小于index2

输入：numbers = {2, 7, 11, 15}, target = 9 (注意：输入的数组不一定有序)

输出：index1 ＝ 0， index2 ＝ 1

Approach #1 (Brute Force)

Analysis

首先看到题目之后，很容易就能想到O(n^2)的方法，就是通过双重循环遍历数组中所有元素的两两结合，当出现符合的target时返回两个元素的索引。注意内存循环应该从外层循环索引的下一个开始搜索，避免查找到两个相同的元素。

Code

import java.util.*;
class TwoSum {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        for (int i=0; i<numbers.length; i++) {
            for (int j=i+1; j<numbers.length; j++) {
                if (numbers[j] == target - numbers[i]) {
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }
}
// leetcode很好的一点就是不用考虑输入输出，只需要提交你的解决方案
// 这是我自己写的一个输入输出测试，Java语言处理输入有点烦。。
public class Solution001{
    public static void main(String[] args){
        int count = 0;
        int target;
        int[] numbers = new int[10];
        int[] temp = new int[10];
        int[] results = new int[2];
        Scanner in = new Scanner(System.in);
        System.out.println("please give an array of intergers and a target:");
        while(in.hasNextInt())
            temp[count++] = in.nextInt();
        target = temp[count-1];
        for(int i=0; i<count-1; i++)
            numbers[i] = temp[i];
        TwoSum ts = new TwoSum();
        results = ts.twoSum(numbers, target);
        System.out.print(results[0] + " " + results[1]);
        System.out.println();
    }
}

Complexity

时间复杂度：O(n^2)

空间复杂度：O(1)O(1)

Approach #2 (Two-pass Hash Table)

Analysis

为了改善运行时的复杂度，我们需要一种更有效的方法来检查数组中是否存在互补。如果存在互补，我们需要查找它的索引。将数组中每个元素映射到其索引的最好方法是什么？很容易就联想到了哈希表。

我们减少了查找时间从O(n)到O(1)的交易空间的速度。哈希表是为这个目的而建立的，它支持在近恒定时间内快速查找。所谓“近”，是因为如果发生碰撞，查找可能退化为O(n)的时间。但哈希表查找应摊销O(1)的时间，只要散列函数仔细选择。

一个简单的实现使用两个迭代。第一次遍历数组先将所有元素和它的下标作为key-value对存入Hashmap中，第二次遍历数组时根据目标和与当前元素之差，在Hashmap中找相应的差值。如果存在该差值，说明存在两个数之和是目标和。此时记录下当前数组元素下标并从Hashmap中取出数组元素下标即可。Hashmap获取元素的时间复杂度是O(1)，所以总的时间复杂度仍不超过O(n)。

注意：判定是否存在该差值时，要同时判断该差值的下标是不是当前遍历的元素下标，以避免重复。

Code

public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map<integer integer=""> map = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        map.put(numbers[i], i);
    }
    for (int i = 0; i < numbers.length; i++) {
        int complement = target - numbers[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            result[0] = i;
            result[1] = map.get(complement);
            return result;
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Complexity

时间复杂度：O(n)

空间复杂度：O(1)O(n)

Approach #3 (One-pass Hash Table)

Analysis

可以对Two-pass Hash Table进行优化，通过一次遍历即可。当我们在表中进行迭代和插入元素时，我们也回头检查表中是否存在当前元素的互补。如果它存在，我们已经找到一个解决方案，并立即返回。

Code

public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map<integer integer=""> map = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        map.put(numbers[i], i);
    }
    for (int i = 0; i < numbers.length; i++) {
        int complement = target - numbers[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            result[0] = i;
            result[1] = map.get(complement);
            return result;
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Complexity

时间复杂度：O(n)

空间复杂度：O(1)O(n)

Approach #4 (Sorting With Two Pointers)

Analysis

问题描述：在一个数组（无序）中快速找出两个数字，使得两个数字之和等于一个给定的值。假设数组中肯定存在至少一组满足要求。

《剑指Offer》P214（有序数组）《编程之美》P176

容易想到在有序数组中进行查找。首先将原数组复制一遍，对新数组进行排序。排序后将双指针指向头部与尾部元素，进行迭代。如果双指针指向元素之和大于目标和，则将尾部指针向前移一位，反之则将头部指针向后移一位，直到双指针指向元素之和等于目标和，记录这两个元素的值，然后再遍历一遍旧数组，找出这两个元素的下标。

Code

public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    int[] nums = new int[numbers.length];
    for (int i = 0; i < numbers.length; i++) { // 复制数组
        nums[i] = numbers[i];
    }
    if(nums == null || nums.length < 2)
        return null;
    Arrays.sort(nums); // 数组排序
    int left = 0;
    int right = nums.length - 1;
    while(left < right) {
        if(nums[left] + nums[right] == target) {
            for (int i = 0; i < numbers.length; i++) {
                if(numbers[i] == nums[left])
                    result[0] = i;
            }
            for (int i = 0; i < numbers.length; i++) {
                if(numbers[i] == nums[right] && i != result[0]) // 避免查找到两个相同元素
                result[1] = i;
            }
            if (result[0] > result[1]) { // 保证找到的第一个整数索引比第二个要小
                int temp = result[0];
                result[0] = result[1];
                result[1] = temp;
            }
            return result;
        } else if(nums[left] + nums[right] > target)
        right--;
        else
            left++;
    }
    return null;
}

Complexity

时间复杂度：O(nlogn)

空间复杂度：O(1) 取决于排序算法